1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/code/kmp.code	Tue Feb 22 19:02:39 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