Ооо, кажется я придумал решение за $$$O(n \cdot \log^2n)$$$

1. Построим суффмассив строки $$$s + t$$$. Найдем теперь просто все вхождения строки $$$s[l_1 \ldots r_1]$$$ в полученную строку. Ну это вроде довольно просто — надо от позиции $$$l_1$$$ в суффиксном массиве отойти влево и вправо до тех пор, пока $$$LCP$$$ не станет меньше $$$r_1 - l_1 + 1$$$. За $$$O(ans)$$$ это делать не хочется, поэтому можно построить дерево отрезков над массивом $$$LCP$$$ на минимум, и бинарным поиском искать первый момент времени, когда $$$LCP$$$ станет меньше нужного числа. Это будет работать за $$$O(\log^2n)$$$. Можно придумать, как это делать быстрее за $$$O(\log n)$$$ одним спуском по дереву, но из-за дальнейшего алгоритма это не нужно. Главное, что мы получили в п.1 — весь отрезок вхождений искомой строки в строку $$$s + t$$$.

2. Теперь нужно оттуда выделить только те строки, которые лежат в $$$l_2 \ldots r_2$$$. По сути, нам надо найти те строки, которые начинаются в отрезке $$$l_2 \ldots r_2 - (r_1 - l_1 + 1)$$$. Т.е. мы свели задачу к поиску количества чисел на отрезке, которые лежат в данном промежутке. Я знаю два решения этой задачи:

1. Заведем дерево отрезков над суффиксным массивом, в каждой вершине ДО будем хранить декартово дерево по явному ключу. В декартовом дереве будем хранить все индексы суффиксного массива, которые лежат на отрезке, за который отвечает вершина дерева отрезков. Теперь, чтобы получить количество чисел, которые лежат в интервале $$$l_2 \ldots r_2 - (r_1 - l_1 + 1)$$$ на данном отрезке, достаточно пройтись по дереву отрезков и в каждой рассмотренной вершине сплитить декартово дерево по $$$l_2$$$ и $$$r_2 - (r_1 - l_1 + 1)$$$ и смотреть на размер среднего дерева. Не забудьте потом смерджить декартово дерево обратно! Преимущество такого подхода — можно в онлайне менять массив. У нас изменений нет, поэтому есть второй подход:

2. Заметим, что в суффиксном массиве мы храним индексы, а значит, числа маленькие (не превосходят суммы длин строк). Поэтому давайте заведем дерево отрезков на сумму, в $$$i$$$-й ячейке будем хранить, есть ли в ДО строка, начинающаяся в $$$i$$$-м символе или нет. Например, ДО от всей строки будет содержать одни единицы, а ДО от пустой строки — одни нули. Такие ДО нам бесполезны, поэтому мы их заведем для каждого префикса сконкатенированной строки. Кажется, что сейчас мы потратили $$$n^2$$$ памяти, ведь у нас $$$n$$$ деревьев отрезков, в каждом хранится $$$n$$$ памяти. Выход — будем использовать персистентное дерево отрезков. Теперь, когда от нас просят найти на отрезке $$$l \ldots r$$$ количество индексов, которые лежат в данных пределах, мы делаем это для префикса $$$r$$$, и из получившегося числа вычитаем это количество для префикса $$$l - 1$$$. Для каждого префикса получать это довольно просто — нужно находить сумму в дереве отрезков для соответствующего префикса. Преимущество такого подхода — скорость, время работы составит $$$O(\log n)$$$.

Так что если вы попробовали первый, и он не зашел по времени — рекомендую сделать спуск по дереву и персистентные деревья отрезков.

P.S. извините за нумерацию, я не знаю, как ее нормально сделать(((

If you preprocess the lcp array on the suffix array, you can get lcp of two suffixes in O(1) as it is just RMQ, which can be achieved with sparse table. Now you have lcp of any two substrings in O(1), so comparing any two substrings lexicographicly is also in O(1), what leads to binsearch in just O(logn), not including the length of substring in the complexity.

More details

I solved it with a different approach.

Concatenate the two string with a diameter in between (S $ T) and build both suffix array and LCP array. Now for each query, find the range in the suffix array which contain the the substring from S, this can be done with binary search and sparse table.

After you find such range for each query, the answer for that query is the number of indices in its range that have values between [L, R-len+1], where L and R are represent the range from T for that query, and len is the length of the substring we're counting.

To count those values, you can either build a segment tree with each node being a sorted vector, and do a binary search on it ( O(n*log^2(n) + m*log^2(n), probably won't get 100 score), or you can process the queries offline. the answer for some query with corresponding range [a, b] in the suffix array, is :

Ans = (Number of values >= L in [a,b]) + (Number of values <= R-len+1 in [a,b]) — ( Length of [a,b] )

So, you can update values from 0 to |S|+|T| in order and find the (Number of values >= L), and similarly for the (Number of values <= R-len+1)

My Submission

P.S: I'm using an O(n) suffix array algorithm, and its code is just unreadable XD.