Good-Suffix-Heuristik

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

(Vorsicht: ist keine Äquivalenzrelation)

$$\gamma{^\prime} \to$$ :

$$\mapsto \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. \begin{array}{ll}& 0 \le k< \vert m\vert \\ \wedge & m[j+1\dots \vert m\vert] \sim m[1\dots k] \end{array} \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:

m a b a b b a b c a b

j 1 2 3 4 5 6 7 8 9 10

$$\gamma{^\prime}$$ 2 2 2 2 2 2 2 7 7 9

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