36 lines
1.2 KiB
Text
36 lines
1.2 KiB
Text
BEGIN
|
|
|
|
INTEGER PROCEDURE LEVENSHTEINDISTANCE(S1, S2); TEXT S1, S2;
|
|
BEGIN
|
|
INTEGER N, M;
|
|
N := S1.LENGTH;
|
|
M := S2.LENGTH;
|
|
IF N = 0 THEN LEVENSHTEINDISTANCE := M ELSE
|
|
IF M = 0 THEN LEVENSHTEINDISTANCE := N ELSE
|
|
BEGIN
|
|
INTEGER ARRAY D(0:N, 0:M);
|
|
INTEGER I, J;
|
|
FOR I := 0 STEP 1 UNTIL N DO D(I, 0) := I;
|
|
FOR I := 0 STEP 1 UNTIL M DO D(0, I) := I;
|
|
S1.SETPOS(1);
|
|
FOR I := 1 STEP 1 UNTIL N DO
|
|
BEGIN
|
|
CHARACTER SI, TJ;
|
|
SI := S1.GETCHAR;
|
|
S2.SETPOS(1);
|
|
FOR J := 1 STEP 1 UNTIL M DO
|
|
BEGIN
|
|
INTEGER COST;
|
|
TJ := S2.GETCHAR;
|
|
COST := IF SI = TJ THEN 0 ELSE 1;
|
|
D(I, J) := MIN(D(I - 1, J) + 1, MIN(D(I, J - 1) + 1, D(I - 1, J - 1) + COST));
|
|
END;
|
|
END;
|
|
LEVENSHTEINDISTANCE := D(N, M);
|
|
END;
|
|
END LEVENSHTEINDISTANCE;
|
|
|
|
OUTINT(LEVENSHTEINDISTANCE("kitten", "sitting"), 0); OUTIMAGE;
|
|
OUTINT(LEVENSHTEINDISTANCE("rosettacode", "raisethysword"), 0); OUTIMAGE;
|
|
|
|
END
|