LCP array: Difference between revisions

Revision as of 02:43, 7 April 2021

Revision as of 06:09, 18 April 2021

Line 45:

== Example ==

Consider the string <math>S = \textrm{banana\$}</math>:

{| class="wikitable"

Line 107:

|}

So, for example, <math>H[3]=3</math> is the length of the longest common prefix <math>\text{ana}</math> shared by the suffixes <math> A[3] = S[4,7] = \textrm{ana\$} </math> and <math>A[4] = S[2,7] = \textrm{anana\$}</math>. Note that <math>H[1]</math> is undefined, since there is no lexicographically smaller suffix.

== Efficient construction algorithms ==