\documentclass[12pt]{article}

\newcommand{\coursenumber}{CS 5124}
\newcommand{\coursetitle}{Algorithms in Bioinformatics}
\newcommand{\thisdocdate}{August 25, 2004}
\newcommand{\doctitle}{Intuition for the $Z$ Algorithm}

\newcommand{\firstpageheading}[1]{
\vbox to 0pt{\vskip -#1
\hbox to \hsize{\sl \vbox to 8.5pt{}%
\coursenumber\hfill\doctitle\hfill\thisdocdate\hfill \rm 1}\vss}
\nointerlineskip
\vspace*{-15pt}
}

\pagestyle{myheadings}
\markboth%
{\doctitle\qquad\thisdocdate\qquad\coursenumber}%
{\doctitle\qquad\thisdocdate\qquad\coursenumber}

\addtolength{\textwidth}{1.00in}
\addtolength{\textheight}{1.00in}
\addtolength{\evensidemargin}{-0.50in}
\addtolength{\oddsidemargin}{-0.50in}
\addtolength{\topmargin}{-0.50in}

\begin{document}

\firstpageheading{50pt}

\thispagestyle{empty}

\begin{center}
\Large\bf\doctitle
\end{center}

The string $S = S[1..n]$
is processed left to right.
In the general case,
$3 \geq k \geq n$,
and we know the $Z_i$, $l_i$, and $r_i$ values
for $2\leq i \leq k-1$.

The string
\begin{eqnarray*}
\alpha & = & S[l_{k-1}..r_{k-1}]
\end{eqnarray*}
is the ``furthest'' $Z$-box found so far.
Hence,
\begin{eqnarray*}
\alpha & = & S[l_{k-1}..r_{k-1}] \\
& = & S[1..Z_{k-1}];
\end{eqnarray*}
if $l_{k-1}=0$,
then all of these are the empty string $\epsilon$.
The value
\begin{eqnarray*}
k' = k - l_{k-1} + 1
\end{eqnarray*}
is the length of the prefix of $S[l_{k-1}..r_{k-1}]$
that is before $S(k)$.
We can write these equalities:
\begin{eqnarray*}
S[l_{k-1}..r_{k-1}]
& = & S[1..Z_{k-1}] \\
S(1) & = & S(l_{k-1}) \\
S(k') & = & S(k) \\
S(Z_{k-1}) & = & S(r_{k-1}).
\end{eqnarray*}

Since the algorithm has matched through $S(Z_{k-1}) = S(r_{k-1})$,
the interval
\begin{eqnarray*}
\beta & = & S[k..r_{k-1}]
\end{eqnarray*}
is the ``furthest''
interval starting at position that has been explored so far.
Moreover,
we know that
\begin{eqnarray*}
S[k..r_{k-1}] & = & S[k'..Z_{k-1}].
\end{eqnarray*}

We can illustrate our status as this:
\begin{displaymath}
\overbrace{S(1) \cdots \underbrace{S(k') \cdots S(Z_{k-1})}_{\beta}}^{\alpha}
\cdots
\overbrace{
S(l_{k-1}) \cdots \underbrace{S(k) \cdots S(r_{k-1})}_{\beta}}^{\alpha}
.
\end{displaymath}
Since we know $Z_k'$,
we can compare it to $r_{k-1}-k+1$ to determine how much of
$S[k..r_{k-1}]$ can be part of a prefix of $S$.
The cases in the algorithm follow from these observations.

\end{document}
