The Suffix-Function

Given a pattern P[1..m], define the suffix-function tex2html_wrap_inline416 such that tex2html_wrap_inline418 is the length of the longest prefix of P that is also a suffix of x:

tex2html_wrap_inline424 

 P = abaabc
   tex2html_wrap_inline336 
   tex2html_wrap_inline430 
   tex2html_wrap_inline432 
   tex2html_wrap_inline434 


 tex2html_wrap_inline436
next up previous
Next: String-Matching Automata Up: STRING MATCHING WITH FINITE Previous: Example