\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
\usepackage{graphicx}
%\usepackage[latin1]{inputenc}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{typearea}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{fullpage}
\usepackage{mathtools}
\usepackage[all]{xy}
\title{Theory I, Sheet 7 Solution}
\author{Eugen Sawin}
\renewcommand{\familydefault}{\sfdefault}
\include{pythonlisting}

\pagestyle{empty}
\begin{document}
\maketitle

\section*{Exercise 7.1}
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. 

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.
\begin{python}
def kmp(text, pattern):    
    l = []
    n = next(pattern)
    j = 0
    for i in range(len(text)):        
        while j >= 0 and text[i] != pattern[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
\end{python}

\subsection*{1}
\begin{align*}
P &= rlrrlr\\
next &= [0, 0, 1, 1, 2, 3]\\
\end{align*}

\subsection*{2}
\begin{align*}
P' &= rrllrrll\\
next &= [0, 1, 0, 0, 1, 2, 3, 4]\\
\end{align*}

\subsection*{3}
\begin{align*}
P &= rlrrlr\\
T &= lrrrlrrlllrrrlrrlrrllrlrrlrrlr\\
next &= [0, 0, 1, 1, 2, 3]\\
matched &= [12, 21, 24]\\
\end{align*}
You can find the full KMP-execution table in the attached text file \emph{kmp-output.txt}.

\section*{Exercise 7.2}
\begin{figure}[h]
\entrymodifiers={+[F-]}
\xymatrix
{
  &   & C & H & U & P & A & C & A & B & R & A  & S\\
  & 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\\
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\\
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\\
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\\
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\\
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]\\
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\\
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\\
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\\
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]\\
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\\
A & 11 & 10& 10& 10& 10& 9\ar[r] & 10& 9 & 8 & 7 & 6 \ar@{-->}[r]  & 7\\
}
\end{figure}
\newpage
\noindent We specify the edit operations:
\begin{enumerate}
\item replace A with C
\item insert H
\item replace B with U
\item replace R with P
\item keep A
\item keep C
\item keep A
\item delete D
\item delete A
\item keep B
\item keep R
\item keep A
\item insert S
\end{enumerate}
And we get $D(A, B) = 7$.
\end{document}
