diff -r ceae9bb06f42 -r 0d0e9abd157b code/kmp.code
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/code/kmp.code	Tue Feb 22 19:02:39 2011 +0100
@@ -0,0 +1,34 @@
+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;
\ No newline at end of file