Good-Suffix Heuristic

Propose to shift the pattern to the right by the least amount that guarantees not to skip any occurrence of the good-suffix already matched. 

T = abbbaabab
           ||
P =    cabaab
P =       cabaab

tex2html_wrap_inline358 (j is the currently

In example above, j = 4, want maximum k such that tex2html_wrap_inline366 

  tex2html_wrap_inline368 


 tex2html_wrap_inline370 


 tex2html_wrap_inline372 


 tex2html_wrap_inline374 


 tex2html_wrap_inline376

so tex2html_wrap_inline378

next up previous
Next: Good-Suffix Heuristic Algorithm Up: BOYER-MOORE Previous: Similarity Relation