Задачник Базовый курс EN

Самый длинный общий кусок

хеширование поиск в тексте двоичный поиск похожесть дедупликация

Сцены этого каталога пишут разные авторы, и иногда функция переезжает из файла в файл копированием. Прежде чем вынести общий код в библиотеку, хочется найти самый длинный кусок, который есть в обоих файлах. Программы поиска копий вроде PMD CPD и jscpd сравнивают файлы скользящим хешем Рабина — Карпа; сделайте то же самое для двух текстов.

Найдите самый длинный кусок, который встречается и в первом тексте, и во втором, — подряд идущие знаки, а не подпоследовательность. Среди тестов — настоящие пары файлов сцен каталога, где пробелы и переводы строк сжаты до одного пробела, два куска «Войны и мира» и геномы фагов λ и φX174.

Вход

Две строки: тексты s и t, от 1 до 50 000 знаков каждый. Знаки любые, кроме перевода строки, в том числе русские буквы и пробелы; длина и позиции считаются в знаках.

Выход

Длина L самого длинного общего куска. Если L > 0, через пробел — позиции i и j, с которых он начинается в s и в t (с нуля): s[i..i + L) = t[j..j + L). Если таких мест несколько, подойдёт любое. Если общих знаков нет, выведите 0.

Примеры

Пример 1

Вход

абракадабра
кадабракадабр

Выход

10 0 3

Пример 2

Вход

кот
пёс

Выход

Ограничения

Время · Python: 5000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 13 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Пусть вы умеете быстро отвечать на вопрос «есть ли общий кусок длины L?». Как найти самое большое L, не перебирая все длины подряд?

2Подсказка 2

Если общий кусок длины L есть, то есть и общий кусок длины L − 1 — его начало. Значит, ответ «да» идёт до некоторой длины, а дальше только «нет», и границу находит двоичный поиск.

3Подсказка 3

Как ответить на вопрос для одной длины за линейное время? Положите хеши всех окон длины L первого текста в таблицу и прокатите окно той же длины по второму тексту — это Рабин — Карп сразу со всеми образцами.

4Идея

Двоичный поиск по длине L, а внутри — проверка за O(n + m): хеши окон s длины L в хеш-таблицу, окна t по очереди ищутся в ней. Хеш окна берётся из хешей начал за O(1). Совпадение хешей проверяется сравнением строк, поэтому ответ никогда не бывает ложным, а случайное основание по простому модулю 2⁶¹ − 1 не даёт подготовленному тесту устроить лишние проверки.

5Разбор

Хеши начал обоих текстов и степени основания считаются один раз. Для длины L строится словарь «хеш окна s → его позиция», затем для каждого окна t смотрим, есть ли его хеш в словаре, и если есть — сравниваем буквами. Первое настоящее совпадение даёт позиции. Двоичный поиск идёт по L от 0 до min(n, m) и запоминает позиции последней удачной длины.

Посмотрите на ответы третьего теста: у файлов dynamic-programming-intro.js и dijkstra.js общий кусок в 528 знаков — почти целиком функция marker, которая рисует на карте кружок с буквой старта или финиша: её переписали из одной сцены в другую. В кусках «Войны и мира» самое длинное общее — 33 знака, в двух случайных строках из a и b по 50 000 букв — 30, около 2 log₂ 50 000: столько у случайных строк совпадает просто случайно.

5+Решение

6Сложность

O((n + m) log min(n, m)) в среднем: семнадцать проходов по ста тысячам окон. Таблица наибольших общих суффиксов из учебника — O(n · m), 2,5 миллиарда клеток. Существует и линейное решение — через суффиксный автомат или суффиксный массив с массивом LCP, — но двоичный поиск с хешем пишется за десять минут.

7Типичные ошибки

Таблица n × m. Верна, но не успевает: в Python даже 10⁸ клеток — это минуты.
Подпоследовательность вместо куска. Наибольшая общая подпоследовательность разрешает пропуски; здесь знаки должны идти подряд.
Без проверки буквами. Если доверять совпадению хешей, при неудачном модуле двоичный поиск может уйти вверх по ложному «да» и выдать длину, которой нет. С проверкой ответ «да» всегда честный.
Хеш с переполнением 64 бит. В одиннадцатом тесте две половины строки Туэ — Морса: в них много разных кусков, у которых хеши по модулю 2⁶⁴ совпадают при любом нечётном основании. Без проверки это неверный ответ, с проверкой — лишняя работа.

Алгоритмы задачи

STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи