# HG changeset patch # User Eugen Sawin # Date 1309964417 -7200 # Node ID a3feee84f85884fccf318d3b45e2c00f1dd06e94 # Parent 15594952470f932843e77957e00e6b4cde63afab Exercise 7. diff -r 15594952470f -r a3feee84f858 src/kmp.py --- a/src/kmp.py Mon Jul 04 16:41:40 2011 +0200 +++ b/src/kmp.py Wed Jul 06 17:00:17 2011 +0200 @@ -5,21 +5,42 @@ def main(): args = parse_arguments() print "next ", next(args.pattern) + + for x in range(len(args.text)): + pad = "" + for p in range(2 - len(str(x))): + pad += " " + print str(x) + pad, + print + #print " ".join([str(i) for i in range(len(args.text))]) + for x in range(len(args.text)): + pad = " " + print args.text[x] + pad, + #for i in range(len(args.text)): + # pad = "" + # for x in range(1, len(str(i))): + # pad += " " + # print args.text[i] + pad, + print print kmp(args.text, args.pattern) -def kmp(text, pattern): +def kmp(text, pattern): l = [] n = next(pattern) j = 0 for i in range(len(text)): - while j >= 0 and text[i] != pattern[j]: - #print "mismatch at text %i and pattern %i" % (i, j) - #print "new pattern %i" % (n[j],) + pad = "" + for x in range(1, i-j+1): + pad += " " + print pad + " ".join(pattern[:j+1]), + while j >= 0 and text[i] != pattern[j]: j = n[j] j += 1 if j == len(pattern): + print " matched", l.append(i - len(pattern) + 1) j = n[j] + print return l def next(pattern): diff -r 15594952470f -r a3feee84f858 tex/theory1_ex7.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tex/theory1_ex7.tex Wed Jul 06 17:00:17 2011 +0200 @@ -0,0 +1,108 @@ +\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}