\begin{slide}{Good-Suffix-Heuristik}

$u \sim v :\iff$ $u$ ist Suffix von $v$ oder $v$ ist Suffix von $u$

(Vorsicht: ist keine Äquivalenzrelation)

\begin{eqnarray*}
\gamma' &:& \{1\dots|m|\} \to \{ 1 \dots |m| \} \\
& & j \mapsto 
  \max \left\{ k : 
\begin{array}{ll}& 0 \le k< |m| \\ 
\wedge & m[j+1\dots |m|] \sim m[1\dots k] 
\end{array}
\right\}
\end{eqnarray*}

Beispiel:
\(
\begin{array}{c|cccccccccc}
m       & a & b & a & b & b & a & b & c & a & b \\ \hline
j       & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
\gamma' & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 7 & 7 & 9 
\end{array}
\)

Anwendung:
$ \verb|offset| = |m| - \gamma'[j] $


\end{slide}
