lindenmannm@3: KMP := proc (T::string, P::string)
lindenmannm@3: # Input: Text T und Muster P
lindenmannm@3: # Output: Liste L mit Verschiebungen i,
lindenmannm@3: #         an denen P in T vorkommt
lindenmannm@3:     n := length (T); m := length(P);
lindenmannm@3:     L := []; next := KMPnext(P);
lindenmannm@3:     j := 0;
lindenmannm@3:     for i from 1 to n do
lindenmannm@3:         whilej>0and T[i]!=P[j+1]
lindenmannm@3:             do j := next [j] od;
lindenmannm@3:         if T[i] = P[j+1] then j := j+1 fi;
lindenmannm@3:         if j = m then
lindenmannm@3:             L := [L[] , i-m];
lindenmannm@3:             j := next [j]
lindenmannm@3:         fi;
lindenmannm@3:     od;
lindenmannm@3:     RETURN (L);
lindenmannm@3: end;
lindenmannm@3: 
lindenmannm@3: KMPnext := proc (P : : string)
lindenmannm@3: #Input : Muster P
lindenmannm@3: #Output : next-Array für P
lindenmannm@3:     m := length (P);
lindenmannm@3:     next := array (1..m);
lindenmannm@3:     next [1] := 0;
lindenmannm@3:     j := 0;
lindenmannm@3:     for i from 2 to m do
lindenmannm@3:         while j > 0 and P[i] <> P[j+1]
lindenmannm@3:             do j := next [j] od;
lindenmannm@3:         if P[i] = P[j+1] then j := j+1 fi;
lindenmannm@3:         next [i] := j
lindenmannm@3:     od;
lindenmannm@3:     RETURN (next);
lindenmannm@3: end;