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

Есть две строки s,t. Дано q запросов. На каждый запрос нужно ответить, сколько раз строка s[l1..r1] лежит на отрезке t[l2..r2] (l1,r1,l2,r2 мы читаем в каждом запросе).

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

P.S: Я смогла оптимизировать моё решение (в бинарном поиске можно делать проверку с помощью ещё одного бинарного поиска, проверяя, подходит ли данный подотрезок, с помощью хэшей). Но оно всё равно берёт только 60 баллов (проходит только в том случае, когда длина строки не превышает 100000). Что можно ещё оптимизировать?