Изменения
Нет описания правки
ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
'''return''' ans
=== Избавление от коллизий ===
Проверять две подстроки на совпадение можно с помощью суффиксного массива. Для этого построим суффиксный массив для строки <tex>s + "\#" + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|)</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
==См. также==
*[[Суффиксный массив]]
*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Суффиксный массив]]
