1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/kmp.py	Mon Jul 04 16:41:40 2011 +0200
     1.3 @@ -0,0 +1,44 @@
     1.4 +"""
     1.5 +Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
     1.6 +"""
     1.7 +
     1.8 +def main():   
     1.9 +    args = parse_arguments()
    1.10 +    print "next ", next(args.pattern)
    1.11 +    print kmp(args.text, args.pattern)
    1.12 +
    1.13 +def kmp(text, pattern):
    1.14 +    l = []
    1.15 +    n = next(pattern)
    1.16 +    j = 0
    1.17 +    for i in range(len(text)):
    1.18 +        while j >= 0 and text[i] != pattern[j]:
    1.19 +            #print "mismatch at text %i and pattern %i" % (i, j)
    1.20 +            #print "new pattern %i" % (n[j],)
    1.21 +            j = n[j]
    1.22 +        j += 1
    1.23 +        if j == len(pattern):
    1.24 +            l.append(i - len(pattern) + 1)
    1.25 +            j = n[j]
    1.26 +    return l
    1.27 +
    1.28 +def next(pattern):
    1.29 +    n = [-1]
    1.30 +    j = -1
    1.31 +    for i in range(len(pattern)):        
    1.32 +        while j >= 0 and pattern[i] != pattern[j]:
    1.33 +            j = n[j]        
    1.34 +        j += 1
    1.35 +        n.append(j)        
    1.36 +    return n
    1.37 +
    1.38 +from argparse import ArgumentParser
    1.39 +
    1.40 +def parse_arguments():
    1.41 +    parser = ArgumentParser(description="KMP.")
    1.42 +    parser.add_argument("text", help="the text")
    1.43 +    parser.add_argument("pattern", help="the pattern")     
    1.44 +    return parser.parse_args()
    1.45 +
    1.46 +if __name__ == "__main__":
    1.47 +    main()

     2.1 --- a/tex/theory1_ex6.tex	Mon Jun 27 01:01:33 2011 +0200
     2.2 +++ b/tex/theory1_ex6.tex	Mon Jul 04 16:41:40 2011 +0200
     2.3 @@ -70,7 +70,7 @@
     2.4  &= \sum_{i=1}^{n}\Phi_i - \sum_{i=0}^{n-1}\Phi_i + \sum_{i=1}^{n}t_i\\
     2.5  &= \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i\\
     2.6  \end{align*}
     2.7 -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$.
     2.8 +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$.
     2.9  \[\implies \Phi_n - \Phi_0 + \sum_{i=1}^{n}t_i \geq \sum t_i\]\qed
    2.10  
    2.11  \section*{Exercise 6.3}