Задача про нахождение подстроки в строке с помощью суффиксного массива

Revision ru1, by MissTolochin, 2020-02-26 20:21:02

Сегодня я пыталась решить данную задачу (https://codeforces.net/gym/102069/problem/J).

Вроде бы очевидно, что в данном случае можно использовать суффиксный массив, а затем с помощью бин.поиска найти все нужные подотрезки (причем за O(длины строки, которую нужно найти) проверяем, подходит ли данный подотрезок), затем использовать дерево отрезков, чтобы посчитать ответ. Однако это проходит на первых двух подгруппах (берёт 25 баллов). Есть одна проблема, она заключается в том, что там не гарантируется, что сумма всех подстрок, которые мы должны проверять, не будет превышать какую-либо константу (например, длину строки). Значит, нужно оптимизировать бинарный поиск (то есть находить нужные подотрезки за константу, меньшую, чем O(длины строки, которую нужно найти)). С помощью какой структуры данных это можно сделать?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English MissTolochin 2020-02-27 11:26:06 297
ru3 Russian MissTolochin 2020-02-27 11:25:18 333
en2 English MissTolochin 2020-02-26 20:27:02 205
ru2 Russian MissTolochin 2020-02-26 20:26:00 170
en1 English MissTolochin 2020-02-26 20:22:04 890 Initial revision for English translation
ru1 Russian MissTolochin 2020-02-26 20:21:02 897 Первая редакция (опубликовано)