sawine@10: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
sawine@10: \usepackage{graphicx}
sawine@10: %\usepackage[latin1]{inputenc}
sawine@10: \usepackage{amsmath, amsthm, amssymb}
sawine@10: \usepackage{typearea}
sawine@10: \usepackage{algorithm}
sawine@10: \usepackage{algorithmic}
sawine@10: \usepackage{fullpage}
sawine@10: \usepackage{mathtools}
sawine@10: \usepackage[all]{xy}
sawine@10: \title{Theory I, Sheet 7 Solution}
sawine@10: \author{Eugen Sawin}
sawine@10: \renewcommand{\familydefault}{\sfdefault}
sawine@10: \include{pythonlisting}
sawine@10: 
sawine@10: \pagestyle{empty}
sawine@10: \begin{document}
sawine@10: \maketitle
sawine@10: 
sawine@10: \section*{Exercise 7.1}
sawine@10: For this exercise I've used a slightly different implementation of the KMP algorithm, which is semantically equal to the one presented in the lecture. 
sawine@10: 
sawine@10: In this version the $next$ array is prepended with a $-1$, which I omit from the solutions to correspond to the lecture's algorithm's output.
sawine@10: \begin{python}
sawine@10: def kmp(text, pattern):    
sawine@10:     l = []
sawine@10:     n = next(pattern)
sawine@10:     j = 0
sawine@10:     for i in range(len(text)):        
sawine@10:         while j >= 0 and text[i] != pattern[j]:           
sawine@10:             j = n[j]
sawine@10:         j += 1
sawine@10:         if j == len(pattern):            
sawine@10:             l.append(i - len(pattern) + 1)
sawine@10:             j = n[j]        
sawine@10:     return l
sawine@10: 
sawine@10: def next(pattern):
sawine@10:     n = [-1]
sawine@10:     j = -1
sawine@10:     for i in range(len(pattern)):        
sawine@10:         while j >= 0 and pattern[i] != pattern[j]:
sawine@10:             j = n[j]        
sawine@10:         j += 1
sawine@10:         n.append(j)        
sawine@10:     return n
sawine@10: \end{python}
sawine@10: 
sawine@10: \subsection*{1}
sawine@10: \begin{align*}
sawine@10: P &= rlrrlr\\
sawine@10: next &= [0, 0, 1, 1, 2, 3]\\
sawine@10: \end{align*}
sawine@10: 
sawine@10: \subsection*{2}
sawine@10: \begin{align*}
sawine@10: P' &= rrllrrll\\
sawine@10: next &= [0, 1, 0, 0, 1, 2, 3, 4]\\
sawine@10: \end{align*}
sawine@10: 
sawine@10: \subsection*{3}
sawine@10: \begin{align*}
sawine@10: P &= rlrrlr\\
sawine@10: T &= lrrrlrrlllrrrlrrlrrllrlrrlrrlr\\
sawine@10: next &= [0, 0, 1, 1, 2, 3]\\
sawine@10: matched &= [12, 21, 24]\\
sawine@10: \end{align*}
sawine@10: You can find the full KMP-execution table in the attached text file \emph{kmp-output.txt}.
sawine@10: 
sawine@10: \section*{Exercise 7.2}
sawine@10: \begin{figure}[h]
sawine@10: \entrymodifiers={+[F-]}
sawine@10: \xymatrix
sawine@10: {
sawine@10:   &   & C & H & U & P & A & C & A & B & R & A  & S\\
sawine@10:   & 0\ar@{-->}[dr] \ar[d] \ar[r] & \ar[r]1\ar[dr] & 2\ar[dr]\ar[r] & 3\ar[dr]\ar[r] & 4\ar[dr]\ar[r] & \ar[r]5 & 6\ar[r]\ar[dr] & 7\ar[r] & 8\ar[r] & 9\ar[dr]\ar[r] & 10\ar[r] & 11\\
sawine@10: A & 1\ar[dr] \ar[d] & 1\ar[d]\ar[dr] \ar@{-->}[r] & 2\ar[r]\ar@{-->}[dr] & 3\ar[r]\ar[dr] & 4\ar[dr] & 4\ar[d]\ar[r]\ar[dr] & 5\ar[dr]\ar[r] & 6\ar[r]\ar[dr] & 7\ar[r] & \ar[r]8 & 9\ar[r]  & 10\\
sawine@10: B & 2\ar[dr] \ar[d] & 2\ar[d]\ar[dr] & 2\ar[d]\ar[r]\ar[dr] & 3\ar[r]\ar@{-->}[dr] & 4\ar[r]\ar[dr] & 5\ar[dr] & 5\ar[d]\ar[r]\ar[dr] & 6\ar[dr] & 6\ar[d]\ar[r]\ar[dr] & 7\ar[r] & 8\ar[r]  & 9\\
sawine@10: R & 3\ar[dr] \ar[d] & 3\ar[d]\ar[dr] & 3\ar[d]\ar[dr] & 3\ar[d]\ar[r]\ar[dr] & 4\ar[r]\ar@{-->}[dr] & 5\ar[r] & 6\ar[dr] & 6\ar[r]\ar[dr] & 7 & 6\ar[d]\ar[r]\ar[dr] & 7\ar[r]  & 8\\
sawine@10: A & 4\ar[dr] \ar[d] & 4\ar[dr] & 4\ar[d]\ar[dr] & 4\ar[d]\ar[dr] & 4\ar[d]\ar[dr] & 4\ar[d]\ar[r]\ar@{-->}[dr] & 5\ar[r] & 6\ar[r] & 7 & 7 & 6\ar[d]\ar[r]\ar[dr]  & 7\\
sawine@10: C & 5 \ar[d] & 4\ar[d]\ar[r]\ar[dr] & 5\ar[dr] & 5\ar[d]\ar[dr] & 5\ar[d]\ar[dr] & 5 & 4\ar[d]\ar[r]\ar@{-->}[dr] & 5\ar[r] & 6\ar[r] & 7\ar[dr] & 7\ar[dr]  & 7\ar[d]\\
sawine@10: A & 6 \ar[d] & 5\ar[d]\ar[dr] & 5\ar[d]\ar[r]\ar[dr] & 6\ar[dr] & 6\ar[d] & 5\ar[d]\ar[dr] & 5\ar[d] & 4\ar[r]\ar[dr] \ar@{-->}[d] & 5\ar[r]\ar[dr] & 6\ar[r]\ar[dr] & 7\ar[r]\ar[dr]  & 8\\
sawine@10: D & 7 \ar[d] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[r]\ar[dr] & 7\ar[dr] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[dr] & 5\ar[dr] \ar@{-->}[d] & 5\ar[d]\ar[dr]\ar[r] & 6\ar[r]\ar[dr] & 7\ar[r]  & 8\\
sawine@10: A & 8 \ar[d] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d] & 6\ar[d] \ar@{-->}[dr] & 6\ar[dr] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[dr]\ar[r]  & 7\\
sawine@10: B & 9 \ar[d] & 8\ar[d]\ar[dr] & 8\ar[d]\ar[dr] & 8\ar[d]\ar[dr] & \ar[dr]8\ar[d] & 8\ar[d]\ar[dr] & 8\ar[d] & 7\ar[d] & 6\ar[d]\ar[r] \ar@{-->}[dr] & 7 & 7\ar[dr]  & 7\ar[d]\\
sawine@10: R & 10 \ar[d]& 9\ar[d]\ar[dr] & 9\ar[d]\ar[dr] & 9\ar[d]\ar[dr] & 9\ar[d]\ar[dr] & 9\ar[dr] & 9\ar[d]\ar[dr] & 8\ar[d] & 7\ar[d] & 6\ar[d]\ar[r] \ar@{-->}[dr] & \ar[r]7  & 8\\
sawine@10: A & 11 & 10& 10& 10& 10& 9\ar[r] & 10& 9 & 8 & 7 & 6 \ar@{-->}[r]  & 7\\
sawine@10: }
sawine@10: \end{figure}
sawine@10: \newpage
sawine@10: \noindent We specify the edit operations:
sawine@10: \begin{enumerate}
sawine@10: \item replace A with C
sawine@10: \item insert H
sawine@10: \item replace B with U
sawine@10: \item replace R with P
sawine@10: \item keep A
sawine@10: \item keep C
sawine@10: \item keep A
sawine@10: \item delete D
sawine@10: \item delete A
sawine@10: \item keep B
sawine@10: \item keep R
sawine@10: \item keep A
sawine@10: \item insert S
sawine@10: \end{enumerate}
sawine@10: And we get $D(A, B) = 7$.
sawine@10: \end{document}