Изменения
→Более быстрый поиск
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>
Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов. У любого суффикса в пределах этого диапазона есть префикс, который полностью совпадает с образцом. <br>
Пусть <tex> L </tex> - левая граница диапазона поиска (изначально равна 0), <tex> R </tex> - правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex>. <br>
Пусть <tex> l = lcp(array[L], p) </tex>, а <tex> r = lcp(array[R], p) </tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>. <br>
