Изменения
→Алгоритм
Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона ответов есть префикс, который полностью совпадает с образцом.
В самом начале просто посчитаем <tex> l</tex> и <tex> r </tex> за линейное времяс помощью [[Алгоритм Касаи и др.|алгоритма Касаи, Арикавы, Аримуры, Ли и Парка]], а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>.
Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов <tex> array </tex> из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах. Аналогично любая пара суффиксов <tex> array </tex> из диапазона <tex> [M, R] </tex> имеет хотя бы <tex> m_r </tex> совпадений в префиксах.
