Levenshtein distance: Difference between revisions
Add Modula-2
m (→{{header|BQN}}) |
Not a robot (talk | contribs) (Add Modula-2) |
||
Line 3,420:
=={{header|Modula-2}}==
<lang modula2>MODULE LevenshteinDistance;
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
FROM Strings IMPORT Length;
PROCEDURE levenshtein(s, t: ARRAY OF CHAR): CARDINAL;
CONST MaxLen = 15;
VAR d: ARRAY [0..MaxLen],[0..MaxLen] OF CARDINAL;
lenS, lenT, i, j: CARDINAL;
PROCEDURE min(a, b: CARDINAL): CARDINAL;
BEGIN
IF a<b THEN RETURN a;
ELSE RETURN b;
END;
END min;
BEGIN
lenS := Length(s);
lenT := Length(t);
IF lenS = 0 THEN RETURN lenT;
ELSIF lenT = 0 THEN RETURN lenS;
ELSE
FOR i := 0 TO lenS DO d[i,0] := i; END;
FOR j := 0 TO lenT DO d[0,j] := j; END;
FOR i := 1 TO lenS DO
FOR j := 1 TO lenT DO
IF s[i-1] = t[j-1] THEN
d[i,j] := d[i-1,j-1];
ELSE
d[i,j] :=
min(d[i-1,j] + 1,
min(d[i,j-1] + 1, d[i-1,j-1]+1));
END;
END;
END;
RETURN d[lenS,lenT];
END;
END levenshtein;
PROCEDURE ShowDistance(s, t: ARRAY OF CHAR);
BEGIN
WriteString(s);
WriteString(" -> ");
WriteString(t);
WriteString(": ");
WriteCard(levenshtein(s, t), 0);
WriteLn();
END ShowDistance;
BEGIN
ShowDistance("kitten", "sitting");
ShowDistance("rosettacode", "raisethysword");
END LevenshteinDistance.</lang>
{{out}}
<pre>kitten -> sitting: 3
rosettacode -> raisethysword: 8</pre>
=={{header|NetRexx}}==
| |||