Я прочитал, что Самый длинный общий префикс (LCP) можно использовать для поиска числа вхождений шаблона в строке.
В частности, вам просто нужно создать массив суффиксов текста, отсортировать его, а затем вместо выполнения двоичного поиска найти диапазон, чтобы вы могли определить количество вхождений, вы просто вычисляете LCP для каждого последующего запись в массив суффиксов.
Хотя использование двоичного поиска для поиска количества вхождений шаблона очевидно, я не могу понять, как LCP помогает найти количество вхождений здесь.
Например, для этого массива суффиксов для banana
:
LCP Suffix entry
N/A a
1 ana
3 anana
0 banana
0 na
2 nana
Как помочь LCP найти количество вхождений подстроки типа "банан" или "na", не очевидно для меня.
Любая помощь в определении того, как LCP помогает здесь?