| author | Eugen Sawin <sawine@me73.com> |
| Sat, 05 Mar 2011 15:27:15 +0100 | |
| changeset 10 | 3789f490c8f3 |
| permissions | -rw-r--r-- |
1 KMP := proc (T::string, P::string)
2 # Input: Text T und Muster P
3 # Output: Liste L mit Verschiebungen i,
4 # an denen P in T vorkommt
5 n := length (T); m := length(P);
6 L := []; next := KMPnext(P);
7 j := 0;
8 for i from 1 to n do
9 whilej>0and T[i]!=P[j+1]
10 do j := next [j] od;
11 if T[i] = P[j+1] then j := j+1 fi;
12 if j = m then
13 L := [L[] , i-m];
14 j := next [j]
15 fi;
16 od;
17 RETURN (L);
18 end;
20 KMPnext := proc (P : : string)
21 #Input : Muster P
22 #Output : next-Array für P
23 m := length (P);
24 next := array (1..m);
25 next [1] := 0;
26 j := 0;
27 for i from 2 to m do
28 while j > 0 and P[i] <> P[j+1]
29 do j := next [j] od;
30 if P[i] = P[j+1] then j := j+1 fi;
31 next [i] := j
32 od;
33 RETURN (next);
34 end;