Изменения
→Более быстрый поиск
Существует более быстрый алгоритм поиска образца в строке. Для этого используется lcp (longest common prefix). <br>
Пусть при построении суффиксного массива для строки <tex> s </tex> был построен еще и массив <tex> LCP </tex>, <tex> i </tex>-ой позиции которого соответствует наибольший общий префикс <tex> i </tex>-ого и <tex> (i+1) </tex>-ого суффиксов. <br>
Пусть <tex> L L_p </tex> - левая граница текущего диапазона (изначально равна 10), а <tex> R R_p </tex> - правая граница текущего диапазона (изначально равна длине строки<tex> |S| - 1 </tex>).
==Литература==
* http://habrahabr.ru/blogs/algorithm/115346/
