G. Общая подстрока двух строк

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

Тот же двоичный поиск

Свойство «есть общая подстрока длины $L$» монотонно, поэтому длина ищется двоичным поиском. Проверка: собрать хеши всех кусков длины $L$ первой строки в множество и пройти по кускам второй.

Сложность $O((n + m) \log n)$ при сортировке или хеш-таблице. Это принципиально лучше квадратичной динамики из прошлого занятия, где ограничение было 2500, а здесь - $10^5$.

Почему динамика тут не проходит

Динамика «наибольший общий суффикс префиксов» требует таблицы $n \times m$: при $10^5$ это $10^{10}$ ячеек. Даже свёрнутая до двух строк, она требует $10^{10}$ операций по времени. Хеши убирают именно перебор пар позиций.

Ловушка сравнения

Если сравнивать хеши по одному модулю $10^9$, при $2 \cdot 10^5$ кусков ожидаемое число ложных совпадений около 20 - и ответ будет завышен. Два модуля обязательны. Проверить это легко: посчитайте ответ обеими схемами на строке из одной буквы.

Подробнее: «Сравнение подстрок».

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

Выведите длину наибольшей общей подстроки. Если общих подстрок нет, выведите 0.