Вопрос в следующем — можно ли решить эту задачу(возможно, с долгим предпосчетом) быстрее, чем за линейное время? Я пока дошёл только до вычисления полиномиального хеша и сравнения двух подстрок за единицу, но перебрать их всё равно нужно O(n) Может, запоминать все позиции букв и идти только по префиксам с концом в букве, на которую заканчивается суффикс?