Можно найти длину максимального префикса совпадающего с суффиксом используя бинарный поиск(если префикс длины mid совпадает с суффиксом то префикс длины mid — 1 тоже совпадает с суффиксом)

Что мешает считать $$$O(n)$$$ перебор за «долгий предподсчет»?

Вообще, эта задача решается префикс-функцией.

Как понимать «быстрее, чем за линейное время»? Строку, как минимумом, нужно считать(сгенерировать) за O(n). В строке есть какие-то изменения?

Сначала научимся решать эту задачу для любого префикса заданной строки с преподсчетом за $$$O(n)$$$.

Насчитаем массив префикс функций $$$p$$$ (ссылка есть в комментарии выше). Таким образом мы узнаём для $$$i$$$-й позиции длину совпадающего префикса, что и является ответом на вышепоставленную задачу. Если поступает запрос про префикс строки, просто отвечаем $$$p_i$$$.

Чтобы находить ответ на любую подстроку, нужно заметить, что любую подстроку можно представить как префикс некоторого суффикса. Значит можно насчитать префикс функцию для всех суффиксов за $$$O(n^2)$$$ и отвечать на запрос за $$$O(1)$$$.

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

https://codeforces.net/gym/100962/problem/D