Одинаковые куски
Корректор готовит новое издание и сверяет повторы: в романе одна и та же фраза может встретиться в разных главах, и важно, чтобы в обоих местах она была набрана одинаково. Программа вёрстки задаёт ему вопросы вида «совпадают ли len знаков, начиная с позиции a, и len знаков, начиная с позиции b?». Вопросов много, а куски бывают длиной в десятки тысяч знаков, поэтому сравнивать их по буквам слишком долго.
Ответьте на все вопросы. Среди тестов — начало «Войны и мира» и строка Туэ — Морса из 65 536 букв a и b.
Вход
В первой строке — текст: n знаков (1 ≤ n ≤ 100 000), любые, кроме перевода строки, в том числе русские буквы и пробелы. Во второй — число вопросов q (1 ≤ q ≤ 100 000). Дальше q строк по три числа a, b, len: позиции считаются в знаках с нуля, len ≥ 1, a + len ≤ n и b + len ≤ n.
Выход
q строк: yes, если куски совпадают, и no, если нет.
Примеры
Пример 1
абракадабра 6 0 7 4 1 8 3 0 5 3 0 3 1 0 0 11 0 5 6
yes yes no yes yes no
Пример 2
abbabaabbaababba 4 0 8 8 0 12 4 3 11 2 0 6 3
no yes no yes
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посчитайте один раз хеши всех начал текста и степени основания. Тогда хеш любого куска — одно умножение и вычитание, и вопрос стоит O(1).
2Подсказка 2
Какой модуль взять? Хеш без модуля, с переполнением 64 бит, кажется надёжным: значений 18 квинтиллионов. Посмотрите на четвёртый тест: в строке Туэ — Морса куски по 1024 буквы, начинающиеся с позиций, кратных 1024, бывают двух видов.
3Подсказка 3
Разные куски Туэ — Морса из 1024 букв получают одинаковый хеш по модулю 2⁶⁴ при любом нечётном основании — это теорема из статьи. Нужен простой модуль, и основание лучше выбирать случайно при запуске.
4Идея
Полиномиальный хеш по простому модулю 2⁶¹ − 1 со случайным основанием. Хеши начал H[i] и степени bi считаются за O(n), хеш куска [a, a + len) — это H[a + len] − H[a] · blen по модулю. Ответ «да» на вопрос о разных кусках возможен, но вероятность такой ошибки при случайном основании не больше (len − 1)/p, а на все вопросы вместе — меньше 10⁻⁸.
5Разбор
В Python остаток по 2⁶¹ − 1 считается встроенными длинными целыми. В Go произведение двух остатков занимает до 122 бит: его берут из bits.Mul64, а остаток — из bits.Div64. Основание выбирается генератором случайных чисел при каждом запуске, поэтому никакой заранее подготовленный тест не знает, какие строки для него столкнутся.
Почему не 2⁶⁴? Разность хешей строк Туэ — Морса Sk и Tk равна −(b − 1)(b² − 1)…(b2k−1 − 1), и при нечётном b в ней не меньше 1 + (k − 1)(k + 4)/2 множителей 2. При k = 10 это 64: куски из 1024 букв, один из которых S₁₀, а другой T₁₀, получают один хеш. В четвёртом тесте 40 000 вопросов о таких кусках, и решение с переполнением отвечает «да» на все.
5+Решение
6Сложность
O(n + q) времени и O(n) памяти. Сравнение по буквам стоило бы O(q · len) — до 10⁵ · 10⁵ = 10¹⁰ сравнений на тексте из одной буквы.
7Типичные ошибки
- Переполнение вместо модуля.
unsigned long longв C++,uint64в Go без остатка или& (2**64 − 1)в Python — модуль 2⁶⁴, и строки Туэ — Морса ломают его при любом нечётном основании, а при чётном хватает одинаковых последних 64 букв. - Маленький модуль. По модулю 10⁹ + 7 одно сравнение ошибается с вероятностью около len/10⁹: на ста тысячах вопросов о кусках длиной в тысячи знаков это уже заметно. Возьмите 2⁶¹ − 1 или два модуля.
- Отрицательный остаток. H[a + len] − H[a] · blen бывает отрицательным. В Python
%вернёт неотрицательное число, в Go и C++ — нет: прибавьте модуль перед взятием остатка. - Байты вместо знаков. Позиции в условии считаются в знаках, а русская буква в UTF-8 — два байта. В Go переведите строку в срез рун.