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

Фраза дважды

поиск в тексте разделяй и властвуй редакторы текста олимпиады

При наборе книги в файл бывает, что кусок текста попадает в него дважды подряд: наборщик вернулся к уже набранной строке, распознаватель склеил две страницы, редактор вставил абзац второй раз. В электронном тексте «Войны и мира», которым пользуется этот каталог, так задвоились 57 знаков речи Ланжерона на военном совете в первом томе. Такие места хочется находить программой.

Дан текст из n знаков. Найдите самый длинный кусок, который состоит из двух одинаковых половин, записанных подряд: ww. Если таких несколько, нужен самый левый. Знаки сравниваются как есть: пробелы и знаки препинания считаются, прописная и строчная буквы различаются.

Среди тестов — та самая глава романа, куски романа и английского перевода, геном фага лямбда и текст, в который вставили абзац дважды.

Вход

Одна строка — текст в UTF-8, от 1 до 50 000 знаков; переводов строки внутри нет. Позиции и длины считаются в знаках (буквах Юникода), а не в байтах.

Выход

Два числа через пробел: длина самого длинного куска ww и номер его первого знака (знаки нумеруются с единицы). Если в тексте нет ни одного куска из двух одинаковых половин, выведите 0 0.

Примеры

Пример 1

Вход

Ну, здравствуйте, здравствуйте.

Выход

28 3

Пример 2

Вход

Тук-тук-тук! Кто там?

Выход

8 2

Ограничения

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

Разбор

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

1Подсказка 1

Кусок ww с половиной длины p — это p равенств подряд вида s[i] = s[i + p]. Так получается простое решение: перебрать p от большего к меньшему и пройти по тексту. Сколько это стоит на 50 000 знаков, если самый длинный кусок короткий?

2Подсказка 2

Разделите текст пополам. Кусок ww либо целиком в левой половине, либо целиком в правой, либо пересекает середину. Первые два случая — рекурсия. Как найти все пересекающие середину за линейное время?

3Подсказка 3

Если вторая половина куска начинается левее середины mid, то точка q = mid − p лежит в первой половине. Равенства s[x] = s[x + p] вокруг q — это вопросы «сколько знаков перед q совпадает со знаками перед mid» и «сколько знаков от q совпадает со знаками от mid». На оба сразу для всех p отвечают Z-функции.

4Идея

Алгоритм Мейна и Лоренца из статьи о Z-функции. Для половин u и v считаем четыре Z-функции: перевёрнутой u, склейки v + разделитель + u, склейки перевёрнутых u и v и самой v. Из них для каждой длины половины p получаются k₁ и k₂ — насколько совпадают знаки назад и вперёд от точки q. Кусок с половиной p, пересекающий середину, есть, если k₁ + k₂ ≥ p и k₂ > 0; самое левое его начало — q − min(p − 1, k₁).

5Разбор

Рекурсия по половинам, на каждом уровне — четыре Z-функции и проход по всем p в двух зеркальных случаях. Храним лучшую пару «половина, начало»: длиннее — лучше, при равной длине — левее. Раз меньшие половины уже не нужны, перебор p можно начинать с лучшей найденной.

В третьем тесте ответ — 114 знаков с позиции 6429: «положение неприятеля предполагается известным, тогда как » дважды. Сам повтор длиннее, 125 знаков, но в нём нет куска ww длиннее 114: третья копия обрывается через 11 знаков. В пятом тесте те же 114 знаков даёт молитва Платона Каратаева в английском переводе. В девятом ответ 0 0: это слово Туэ, в котором нет ни одного квадрата, и его строят из последовательности Туэ — Морса, записывая, сколько единиц стоит между соседними нулями.

5+Решение

6Сложность

На каждом уровне рекурсии — O(n), уровней log₂ n ≈ 16, всего O(n log n): около трёх миллионов шагов. Перебор всех p — до 3n²/8 ≈ 940 миллионов сравнений, если самый длинный кусок короткий, как в случайном тексте; на Python это минуты, на Go — несколько секунд.

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

Перебор периодов. Верен, но квадратичен. Он быстро находит задвоенный абзац (там большой кусок попадается первым) и тонет на обычном тексте, где самый длинный кусок из двух половин — пара десятков знаков.
Ограничить длину половины. «Повторы бывают короткими» — и перебор до 1000 знаков пропустит вставленный дважды абзац из десятого теста.
Байты вместо знаков. В UTF-8 русская буква — два байта, и номер позиции в байтах почти вдвое больше. В Go читайте текст как []rune.
Не самый левый. В последнем тесте два куска по 6000 знаков; нужен тот, что начинается раньше.

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

STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи