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

Счётчик сравнений

поиск в тексте подсчёт вариантов предподсчёт

В октябре 2020 года пользователь Python сообщил, что bytes.find зависает на файле из байтов 00 и FF: поиск серии из 15 403 807 байтов FF заканчивался мгновенно, а серии на один байт длиннее — не заканчивался вовсе. Разработчики хотят инструмент, который заранее скажет, сколько работы сделает поиск, не запуская его.

Возьмём поиск из статьи. Образец длины m прикладывают к тексту длины n на каждом сдвиге s = 0, 1, …, n − m и сравнивают буквы слева направо: текст[s] с образцом[0], текст[s + 1] с образцом[1] и так далее, до первого несовпадения или до конца образца. Каждое сравнение двух букв, совпали они или нет, стоит единицу. Поиск не останавливается на первом вхождении: он проходит все сдвиги.

Для текста «колокол» и образца «кол» это 3 + 1 + 1 + 1 + 3 = 9 сравнений. Посчитайте ответ для текстов до ста тысяч букв. Простой прогон поиска не подойдёт: на неудачном тексте он сделает миллиарды сравнений, а именно такие тексты инструмент и должен ловить. Среди тестов — начало «Войны и мира», геном фага λ и уменьшенная копия того самого файла, где вместо байтов 00 и FF буквы x и y.

Вход

Две строки: текст и образец. В них могут быть любые знаки, кроме перевода строки и нулевого байта, в том числе русские буквы и пробелы; строки не начинаются и не заканчиваются пробелом. Длина считается в знаках: 1 ≤ m ≤ n ≤ 100 000.

Выход

Одно число — сколько сравнений букв сделает поиск.

Примеры

Пример 1

Вход

колокол
кол

Выход

Пример 2

Вход

aaaaaaaa
aaab

Выход

Ограничения

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

Разбор

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

1Подсказка 1

Сколько сравнений стоит один сдвиг? Это зависит только от одного числа: сколько букв образца подряд совпадает с текстом начиная с позиции s.

2Подсказка 2

Пусть k — длина общего начала образца и куска текста с позиции s. Если k < m, сдвиг сравнил k совпавших букв и одну несовпавшую: k + 1. Если k = m, сравнений ровно m. Осталось найти k для всех s сразу, быстрее, чем сравнивая.

3Подсказка 3

Склейте образец, разделитель, которого нет в строках, и текст. Для каждой позиции склейки нужна длина её общего начала со всей склейкой. Такой массив называется Z-функцией и считается за линейное время.

4Идея

Цена сдвига s — min(k_s + 1, m), где k_s — длина общего начала образца и текста с позиции s. Все k_s даёт Z-функция строки p + «\0» + t: в позиции m + 1 + s она равна как раз k_s, а разделитель не даёт общему началу перескочить за конец образца. Поиск не запускается вовсе: ответ складывается из чисел, которые он бы получил.

5Разбор

Z-функция считается слева направо. Храним самое правое окно [l, r), про которое уже известно, что оно совпадает с началом строки. Для новой позиции i внутри окна начало совпадения можно взять из уже посчитанного z[i − l], обрезав его по краю окна, и только потом продолжать сравнивать буквы. Каждое удачное сравнение сдвигает правый край окна, поэтому всего их не больше длины строки.

Посмотрите на ответы. На начале «Войны и мира» поиск «князя Андрея» стоит 103 196 сравнений на 99 967 сдвигов, чуть больше одного на сдвиг. На тексте из одних a с образцом a…ab — 2 500 050 000: каждый из 50 001 сдвигов стоит все 50 000 сравнений. В копии файла из 00 и FF байты заменены буквами x и y, серия из 40 000 букв y стоит посреди случайного текста, а образец на одну букву длиннее серии. Ответ — 750 104 190, и почти всё уходит на сдвиги внутри серии: каждый проходит её остаток до конца.

5+Решение

6Сложность

Z-функция — O(n + m) времени и памяти, сумма — O(n). Прямой прогон поиска — O(n · m), в шестом тесте это 2,5 миллиарда сравнений. Можно обойтись и без Z-функции: длину общего начала двух строк находят двоичным поиском, сравнивая куски полиномиальным хешем за O(1). Это O(n log m) и небольшая вероятность ошибки.

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

Запустить поиск и посчитать. Ответ верный, но на тексте из одних a работа квадратичная — та самая, которую инструмент должен предсказывать, не выполняя.
Забыть несовпавшую букву. Сдвиг, на котором совпало k < m букв, стоит k + 1 сравнение, а не k: на «колоколе» получится 6 вместо 9.
Лишнее сравнение на вхождении. Если совпали все m букв, сравнивать больше нечего: m, а не m + 1.
Склейка без разделителя. Общее начало может перескочить из образца в текст, и k выйдет больше m.
32-битный счётчик. Ответ доходит до 2,5 · 10⁹ и не помещается в int32.
Байты вместо знаков. В Go строка — это байты UTF-8, и у «колокола» их 14. Считайте в рунах, иначе сдвигов будет вдвое больше, чем знаков.

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

STR Алгоритм Наивный поиск подстроки Образец прикладывают к каждой позиции текста: n · m сравнений в худшем случае, около n — на обычном тексте. O(n · m) 2 задачи STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи