KMP := proc (T::string, P::string)

# Input: Text T und Muster P

# Output: Liste L mit Verschiebungen i,

#         an denen P in T vorkommt

    n := length (T); m := length(P);

    L := []; next := KMPnext(P);

    j := 0;

    for i from 1 to n do

        whilej>0and T[i]!=P[j+1]

            do j := next [j] od;

        if T[i] = P[j+1] then j := j+1 fi;

        if j = m then

            L := [L[] , i-m];

            j := next [j]

        fi;

    od;

    RETURN (L);

end;

KMPnext := proc (P : : string)

#Input : Muster P

#Output : next-Array für P

    m := length (P);

    next := array (1..m);

    next [1] := 0;

    j := 0;

    for i from 2 to m do

        while j > 0 and P[i] <> P[j+1]

            do j := next [j] od;

        if P[i] = P[j+1] then j := j+1 fi;

        next [i] := j

    od;

    RETURN (next);

end;