Content deleted Content added
m task, replaced: Algorithm Theory - → Algorithm Theory – |
|||
Line 161:
* We continue recursively.
The overall effect is that no character of <math>P</math> is compared to any character of the text more than once (for details see {{sfn|Manber|Myers|1993}}). The total number of character comparisons is bounded by <math>m</math>, so the total complexity is indeed <math>O(m+\log N)</math>.
We still need to precompute LCP-LR so it is able to tell us in <math>O(1)</math> time the lcp between any two entries of the suffix array. We know the standard LCP array gives us the lcp of consecutive entries only, i.e. <math>\mathrm{lcp}(i-1,i)</math> for any <math>i</math>. However, <math>M</math> and <math>M'</math> in the description above are not necessarily consecutive entries.
| |||