%% This LaTeX-file was created by <jl> Mon Apr  6 11:45:28 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}


\section{String Matching}


\subsection{definitions}

\begin{itemize}
\item \( \sum = \) alphabet
\item \( X,Y,Z= \) strings over \( \sum  \)
\item \( XY \) = string \( X \) concatenated with string \( Y \)
\item \( X^{3}=XXX \)
\item \( |X|= \) length of string \( X \)
\item \( Y(i)=i \)th element of \( Y \)
\item \( n=|Y| \)
\item \( m=|X| \)
\end{itemize}

\subsection{string matching problem}

\begin{itemize}
\item input: pattern \( X \), and string \( Y \)
\item output: does \( X \) occur in \( Y \)? \( \exists Z,W:ZXW=Y \)
\end{itemize}
The obvious solution is to check for \( X \) starting at each \( Y(i) \), giving \( O(nm) \)

Less obvious solutions by KMP(Knuth, Morris, and Pratt) and BM (Boyer, Moore)
are \( O(m+n) \) proceed in 2 phases: 

\begin{enumerate}
\item analyze \( X \) so that a failure to match at point \( Y(j) \) starting at \( Y(i) \) will allow you
to restart the pattern match later in \( Y \) than \( Y(i+1) \)
\item Do the pattern match.
\end{enumerate}

\subsection{more definitions}

\begin{itemize}
\item \( X \) a period of \( Y \) if \( Y \) is a prefix of \( X^{\infty } \) and \( |X|<|Y| \)
\item \( Y \) is periodic if \( P\leq \frac{m}{2} \)
\end{itemize}

\subsection{periodicity lemma}

If \( Y \) has periods \( p,q \) with \( p+q\leq m \) then \( Y \) has period \( GCD(p,q) \).


\subsubsection{proof:}

if \( p=q \) done. 

else, assume \( p>q \)


\paragraph{claim:}

\( y \) has period \( p-q \) or \( Y(i)=Y(i+(p-q)) \) for \( 1\leq i\leq m-(p-q) \)


\paragraph{proof:}

\begin{enumerate}
\item \( Y(i)=Y(i+p) \) for \( 1\leq i\leq m-p \)
\item \( Y(i)=Y(i-q) \) for \( q+1\leq i\leq m \)
\item 1+2 \( \Rightarrow  \) \( Y(i-q)=Y(i+p-q) \) for \( q+1\leq i\leq m-p+q \)
\item 2+3 \( \Rightarrow  \) \( Y(i)=Y(i-q) \) \( =Y(i+(p-q)) \) for \( q+1\leq i\leq m-(p-q) \)
\item You can also get: \( Y(i)=Y(i+p)=Y(i+p-q) \) for \( 1\leq i\leq m-p \)
\end{enumerate}
We just need \( m-p\geq q \) to satisfy \( p+q\leq m \). Now, apply Euclids theorem to get that \( Y \) has period
\( GCD(p,q) \)


\subsection{finding periods}

To find the period, \( P \), of \( Y \), just offset \( Y \) by P and check for matching overlaps.


\subsection{Another lemma:}

\( |Y|=m \) with minimum period \( P \) and \( Z \) with \( |Z|=n\geq m \) then 

\begin{enumerate}
\item if \( Y \) occurs in \( Z \) at \( i \) and \( j \) then \( |i-j|\geq p \)
\item if \( Y \) occurs in \( Z \) at \( i \) and \( i+d \) where \( d\leq m-p \) then \( p \) divides \( d \).
\end{enumerate}

\subsubsection{proof:}

if \( i-j\geq m \) then we are done.

The rest of the proof is by pictures. 


\subsection{The witness array}

\( |Y|=m \) and is of size \( min\{P,\frac{m}{2}\} \)

\begin{itemize}
\item \( \phi _{wit}(1)=0 \)
\item \( \phi _{wit}(i)=k\leq m+1-i \) s.t. \( Y(k)\neq Y(i+k-1) \)
\end{itemize}

\section{The algorithm}

\( Duel(i,j) \)

input: pattern \( Y \) plus a witness array and a text, \( Z \) with \( |i-j|\leq (p,\frac{m}{2}) \)

output: return \( i \) or \( j \)

\begin{enumerate}
\item compare \( Y \) to \( Z \) starting at \( Z(i) \) and \( Z(j) \). Check the witness point.
\end{enumerate}
We have eliminated one element of a pair of patterns in unit time. 


\section{text analysis in the nonperiodic case}

Input: pattern \( Y \) with witness vector, text \( Z \)

\begin{enumerate}
\item Divide \( Z \) into chunks, \( T_{i} \) of size \( \frac{m}{2} \)
\item In parallel, check if \( Y \) starts in \( T_{i} \) using \( Duel \).
\item Eliminate all but one occurence by using \( Duel \).
\item Check the last case by brute force.
\end{enumerate}

\subsection{Timing analyses}

\begin{itemize}
\item steps 2 and 3 are \( T(n,m)=log(m) \) and \( W(n,m)=m*\frac{n}{m}=O(n) \)
\item step 4 \( T(n)=log(n) \) and \( W(n,m)=\frac{n}{m}*m=n \)
\end{itemize}
So the total is \( T(n)=log(n) \) and \( W(n)=n \)

\end{document}