\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}