Изменения

Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>

Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов. В пределах этого диапазона в суффиксном массиве <tex> array </tex> лежат суффиксы, префиксы которых полностью совпадают с образцом <tex> p </tex>.

Пусть <tex> L </tex> - левая граница диапазона поиска (изначально равна 0), <tex> R </tex> - правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex>. <br>