Prefix Function

tex2html_wrap_inline322 refers to the first k characters of P (the k length prefix of P).

tex2html_wrap_inline332 

 P = aababddc


 tex2html_wrap_inline336 


 tex2html_wrap_inline338 


 tex2html_wrap_inline340 


etc.

Given a pattern P[1,m], define the prefix-function tex2html_wrap_inline344 :

tex2html_wrap_inline346

Example.

next up previous
Next: Computing the Prefix Function Up: BOYER-MOORE Previous: Good-Suffix Heuristic