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