O. Где стоит общая подстрока

Найдите наибольшую общую подстроку двух строк и укажите, где она стоит в каждой.

Длина ищется как в классе - двоичным поиском по хешам. Дальше надо восстановить позиции, и тут появляется новая тонкость.

После того как длина $L$ найдена, повторяем проверку ещё раз, но теперь запоминаем для каждого хеша наименьшую позицию в первой строке. Потом идём по второй строке слева направо и для каждой позиции, чей хеш нашёлся, получаем пару $(i, j)$.

Из всех пар берём наименьшую: сначала по $i$, при равенстве - по $j$. Поскольку по второй строке мы идём по возрастанию, для фиксированного $i$ первое же найденное $j$ и будет наименьшим.

Если общих подстрок нет вовсе, выведите одно число 0.

Хранить в словаре надо именно минимум позиции, а не первую попавшуюся: одинаковых подстрок в первой строке может быть много, и если класть последнюю, ответ окажется не наименьшим.

В первой строке - строка $s$, во второй - строка $t$.

Обе непусты, состоят из строчных латинских букв, длины не превосходят $10^5$.

Если общей подстроки нет, выведите одно число 0.

Иначе выведите три числа: длину наибольшей общей подстроки и позиции её начала в $s$ и в $t$ (нумерация с единицы), наименьшие в описанном смысле.