1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/code/kmp.code Tue Feb 22 19:14:19 2011 +0100
1.3 @@ -0,0 +1,34 @@
1.4 +KMP := proc (T::string, P::string)
1.5 +# Input: Text T und Muster P
1.6 +# Output: Liste L mit Verschiebungen i,
1.7 +# an denen P in T vorkommt
1.8 + n := length (T); m := length(P);
1.9 + L := []; next := KMPnext(P);
1.10 + j := 0;
1.11 + for i from 1 to n do
1.12 + whilej>0and T[i]!=P[j+1]
1.13 + do j := next [j] od;
1.14 + if T[i] = P[j+1] then j := j+1 fi;
1.15 + if j = m then
1.16 + L := [L[] , i-m];
1.17 + j := next [j]
1.18 + fi;
1.19 + od;
1.20 + RETURN (L);
1.21 +end;
1.22 +
1.23 +KMPnext := proc (P : : string)
1.24 +#Input : Muster P
1.25 +#Output : next-Array für P
1.26 + m := length (P);
1.27 + next := array (1..m);
1.28 + next [1] := 0;
1.29 + j := 0;
1.30 + for i from 2 to m do
1.31 + while j > 0 and P[i] <> P[j+1]
1.32 + do j := next [j] od;
1.33 + if P[i] = P[j+1] then j := j+1 fi;
1.34 + next [i] := j
1.35 + od;
1.36 + RETURN (next);
1.37 +end;
1.38 \ No newline at end of file