# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1309790500 -7200
# Node ID 15594952470f932843e77957e00e6b4cde63afab
# Parent  862ab5c7c6df997791bdac15b365af1678eef35c
KMP.

diff -r 862ab5c7c6df -r 15594952470f src/kmp.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/kmp.py	Mon Jul 04 16:41:40 2011 +0200
@@ -0,0 +1,44 @@
+"""
+Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
+"""
+
+def main():   
+    args = parse_arguments()
+    print "next ", next(args.pattern)
+    print kmp(args.text, args.pattern)
+
+def kmp(text, pattern):
+    l = []
+    n = next(pattern)
+    j = 0
+    for i in range(len(text)):
+        while j >= 0 and text[i] != pattern[j]:
+            #print "mismatch at text %i and pattern %i" % (i, j)
+            #print "new pattern %i" % (n[j],)
+            j = n[j]
+        j += 1
+        if j == len(pattern):
+            l.append(i - len(pattern) + 1)
+            j = n[j]
+    return l
+
+def next(pattern):
+    n = [-1]
+    j = -1
+    for i in range(len(pattern)):        
+        while j >= 0 and pattern[i] != pattern[j]:
+            j = n[j]        
+        j += 1
+        n.append(j)        
+    return n
+
+from argparse import ArgumentParser
+
+def parse_arguments():
+    parser = ArgumentParser(description="KMP.")
+    parser.add_argument("text", help="the text")
+    parser.add_argument("pattern", help="the pattern")     
+    return parser.parse_args()
+
+if __name__ == "__main__":
+    main()
diff -r 862ab5c7c6df -r 15594952470f tex/theory1_ex6.tex
--- a/tex/theory1_ex6.tex	Mon Jun 27 01:01:33 2011 +0200
+++ b/tex/theory1_ex6.tex	Mon Jul 04 16:41:40 2011 +0200
@@ -70,7 +70,7 @@
 &= \sum_{i=1}^{n}\Phi_i - \sum_{i=0}^{n-1}\Phi_i + \sum_{i=1}^{n}t_i\\
 &= \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i\\
 \end{align*}
-By definition we know that $\Phi_0 = -1$ and since $2k-s \geq 0$ for $\alpha \geq \frac{1}{2}$ and $\frac{s}{2}-k \geq 0$ for $\alpha < \frac{1}{2}$ it follows that $\Phi_n - \Phi_0 >= 0$.
+By definition we know that $\Phi_0 = -1$ and since $2k-s \geq 0$ for $\alpha \geq \frac{1}{2}$ and $\frac{s}{2}-k \geq 0$ for $\alpha < \frac{1}{2}$ it follows that $\Phi_n - \Phi_0 \geq 0$.
 \[\implies \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i \geq \sum t_i\]\qed
 
 \section*{Exercise 6.3}