\documentclass[12pt]{article}
\usepackage{graphics,epsfig}

\usepackage{geometry} 

\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\newcommand{\myspan}{\mbox{span}}

\begin{document}

\title{CS 141: Advanced Topics in Algorithms \\ Spring 2006 \\ Homework Alan and Reid}
\author{}
\date{Due:  Thursday, April 27}
\maketitle

\begin{enumerate}

  \item \Points{10} \Name{Proof of KMP's Linear Running Time!}
  Recall from class that the KMP algorithm has the following pseudocode:
  \begin{verbatim}
KMP(P,T):
  pi=Compute-Prefix(P)
  q=0 // Number of characters we've matched so far
  for i=1 to n
    while q>0 && P[q+1]!=T[i]
      q=pi[q]
    if P[q+1]==T[i]
      ++q
    if q==m
      print "Pattern matched, starting at char " (i-m)
  \end{verbatim}
  Given that \texttt{Compute-Prefix(P)} runs in $O(m)$ time, show that the rest of 
  \texttt{KMP(P,T)} runs in $O(n)$ time and that the whole algorithm is therefore
  $O(m+n)$. 
  \end{enumerate}

\end{document}
