Good-Suffix-Heuristik

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

(Vorsicht: ist keine Äquivalenzrelation)


$\displaystyle \gamma{^\prime}$ : {1...| m|}$\displaystyle \to${1...| m|}  
    j $\displaystyle \mapsto$ max$\displaystyle \left\{\vphantom{ k :
\begin{array}{ll}& 0 \le k< \vert m\vert \\
\wedge & m[j+1\dots \vert m\vert] \sim m[1\dots k]
\end{array}}\right.$k : $\displaystyle \begin{array}{ll}& 0 \le k< \vert m\vert \\
\wedge & m[j+1\dots \vert m\vert] \sim m[1\dots k]
\end{array}$$\displaystyle \left.\vphantom{ k :
\begin{array}{ll}& 0 \le k< \vert m\vert \\
\wedge & m[j+1\dots \vert m\vert] \sim m[1\dots k]
\end{array}}\right\}$  

Beispiel:
mababbabcab
j12345678910
$ \gamma{^\prime}$2222222779

Anwendung: offset = | m| - $ \gamma{^\prime}$[j]



Johannes Waldmann 2008-01-24