\documentclass[12pt]{article}

\usepackage{latexsym}

\newcommand{\coursenumber}{CS 5124}
\newcommand{\coursetitle}{Algorithms in Bioinformatics}
\newcommand{\thisdocdate}{August 30, 2004}
\newcommand{\doctitle}{Pseudocode for Fundamental Preprocessing}

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

% Pseudocode line numbering
\newcounter{pseudocode}
\newcommand{\firstline}{\setcounter{pseudocode}{0}\linenumber}
\newcommand{\linenumber}{\refstepcounter{pseudocode}\thepseudocode}

% Comment for pseudocode
\newcommand{\comment}{$\rhd$\ \ }

\begin{document}

\firstpageheading{50pt}

\thispagestyle{empty}

\begin{center}
\Large\bf\doctitle\\[12pt]
The $Z$ Algorithm\footnote{%
Gusfield, Section 1.4.}
\end{center}

\vspace*{40pt}

\begin{tabbing}
\textsc{$Z$-Algorithm}$(S[1..n])$\\[8pt]

\firstline\qquad\=
\comment INPUT: String $S=S[1..n]$ \\
\linenumber\>%
\comment OUTPUT: 
$(Z_k,l_k,r_k)$, for $2 \leq k \leq n$ \\[8pt]

\linenumber\>%
\comment Base case: $k=2$ \\
\linenumber\>%
$Z_2 = n - 1$ \qquad\qquad\=\comment Value if no mismatch found \\
\linenumber\>%
{\bf for} \=$i \leftarrow 2$ {\bf to} $n$ \\
\linenumber\>%
\>{\bf do if} \=$S(i) \not= S(1)$ \\
\linenumber\>%
\>\>{\bf then} \=
\comment Have found a mismatch --- a character not matching $S(1)$ \\
\linenumber\>%
\>\>\>$Z_2 \leftarrow i-2$ \\
\linenumber\>%
\>\>\>{\bf break} \\
\linenumber\>%
{\bf if} \= $Z_2 > 0$ \\
\linenumber\>%
\>{\bf then} \= $l_2 \leftarrow 2$ \\
\linenumber\>%
\>\> $r_2 \leftarrow Z_2 + 1$ \\
\linenumber\>%
\>{\bf else} \> $l_2 \leftarrow r_2 \leftarrow 0$ \\[8pt]

\linenumber\>%
\comment General case: $3 \leq k \leq n$ \\
\linenumber\>%
{\bf for} \=$k \leftarrow 3$ {\bf to} $n$ \\
\linenumber\>%
\>{\bf do if} \=$r_{k-1} < k$\=\qquad\=\qquad\=\qquad\=\qquad
\=\comment Have not matched $S(k)$ yet \\
\linenumber\>%
\>\>{\bf then} \=
$Z_k = n - k + 1$ \>\>\>\>\comment Value if no mismatch found \\
\linenumber\>%
\>\>\>{\bf for} \=$i \leftarrow k$ {\bf to} $n$ \\
\linenumber\>%
\>\>\>\>{\bf do if} \=$S(i) \not= S(i-k+1)$ \\
\linenumber\>%
\>\>\>\>\>{\bf then} \=
\>\comment Have found a mismatch \\
\linenumber\>%
\>\>\>\>\>\>$Z_k \leftarrow i-k$ \\
\linenumber\>%
\>\>\>\>\>\>{\bf break} \\
\linenumber\>%
\>\>\>{\bf if} \= $Z_k > 0$ \\
\linenumber\>%
\>\>\>\>{\bf then} \= $l_k \leftarrow k$ \\
\linenumber\>%
\>\>\>\>\> $r_k \leftarrow k + Z_k - 1$ \\
\linenumber\>%
\>\>\>\>{\bf else} \> $l_k \leftarrow r_k \leftarrow 0$ \\[30pt]

\textsc{Continued}\\[1pt]

\hspace*{1pt}\\[20pt]

\hspace*{1pt}\\[20pt]

\textsc{$Z$ Algorithm Concluded}\\[20pt]

\linenumber\>%
\>\>{\bf else} \=
\>\>\>\>\comment $k$ is in the $Z$-box $[l_{k-1}..r_{k-1}]$ \\
\linenumber\>%
\>\>\>$k' \leftarrow k - l_{k-1}+1$ \\
\linenumber\>%
\>\>\>$\alpha \leftarrow S[l_{k-1}..r_{k-1}]$
\>\>\>\>\comment $S[1..r_{k-1}-l_{k-1}+1] = \alpha$ \\
\linenumber\>%
\>\>\>$\beta \leftarrow S[k..r_{k-1}]$
\>\>\>\>\comment 
$S[k'..r_{k-1}-l_{k-1}+1] = \beta$ \\
\linenumber\>%
\>\>\>{\bf if} \= $Z_{k'} < |\beta|$ \\
\linenumber\>%
\>\>\>\>{\bf then} \= $Z_k \leftarrow Z_{k'}$ \\
\linenumber\>%
\>\>\>\>\>$l_k \leftarrow l_{k-1}$ \\
\linenumber\>%
\>\>\>\>\>$r_k \leftarrow r_{k-1}$ \\
\linenumber\>%
\>\>\>\>{\bf else} \>\>\>\comment $Z_{k'} \geq |\beta|$ \\
\linenumber\>%
\>\>\>\>\>{\bf if} \= $r_k-1 = n$ \\
\linenumber\>%
\>\>\>\>\>\>{\bf then} \= $q \leftarrow n$ \\
\linenumber\>%
\>\>\>\>\>\>{\bf else}\>{\bf for} \= $q \leftarrow r_{k-1}+1$ {\bf to} $n$ \\
\linenumber\>%
\>\>\>\>\>\>\>\>{\bf do} \= {\bf if} \=$S(|\beta|+q-r_{k-1}) \not= S(q)$ \\
\linenumber\>%
\>\>\>\>\>\>\>\>\>\>{\bf then} \= $q \leftarrow q-1$ \\
\linenumber\>%
\>\>\>\>\>\>\>\>\>\>\>{\bf break} \\
\linenumber\>%
\>\>\>\>\> $Z_k \leftarrow q-k+1$ \\
\linenumber\>%
\>\>\>\>\> $l_k \leftarrow k$ \\
\linenumber\>%
\>\>\>\>\> $r_k \leftarrow q$ \\[8pt]

\linenumber\>%
{\bf return} $(Z_k,l_k,r_k)$, for $2 \leq k \leq n$ \\
\end{tabbing}

\end{document}
