Иголка в стоге

Прошлая глава оставила задачу: найти слово в тексте длиной три миллиарда букв быстрее, чем перебором. Этот текст — геном человека. Его копия лежит почти в каждой клетке вашего тела, а алфавит в нём из четырёх букв: A, C, G и T. Глава начинается в генетической лаборатории, где поиск подстроки — работа на каждый день, а заканчивается в школьной комиссии, которая разбирает подозрительно похожие сочинения. Инструменты там и там понадобятся одни и те же.

Лаборатория. Три миллиарда букв

Начнём с генома поменьше человеческого, но побольше, чем у φX174. Бактериофаг лямбда — рабочая лошадка молекулярной биологии: его ДНК продают в пробирках, и на нём проверяют новые методы. Его геном — 48 502 буквы. Лаборатории хранят геномы в формате FASTA: первая строка начинается со знака > и описывает, что это за последовательность, а дальше идут буквы, по 70 в строке. Файлы трёх геномов из открытой базы NCBI лежат в папке /data/strings-search: фаг φX174, фаг лямбда и митохондрия человека.

Первое задание лаборатории — предсказать опыт. У бактерий есть белки-ножницы, ферменты рестрикции: каждый узнаёт в ДНК свой короткий мотив и режет молекулу в этом месте. Фермент EcoRI из кишечной палочки ищет мотив GAATTC и режет его после первой буквы. Если знать все вхождения мотива, можно заранее сказать, на какие куски распадётся ДНК. Искать пока будем методом find из главы 7: он возвращает позицию вхождения или −1, а второй аргумент говорит, с какой позиции начинать.

Пять разрезов, шесть кусков: 21 226, 7421, 5804, 5643, 4878 и 3530 букв. Если обработать ДНК лямбды ферментом EcoRI и пустить её по гелю в электрическом поле, куски разойдутся по длине, и на геле проступят шесть полос как раз таких длин. Такую смесь продают готовой и пользуются ею как линейкой, чтобы мерить другие молекулы. Десяток строк Python предсказал опыт, который ставят в лаборатории.

Прочитайте мотив GAATTC задом наперёд и замените каждую букву парной — A на T, C на G и наоборот. Получится снова GAATTC. ДНК — две нити, и вторая читается именно так, поэтому фермент узнаёт мотив на обеих нитях сразу. Биологи называют такие мотивы палиндромами, хотя это палиндром с поправкой — не тот, что мы проверяли в главе 7.

Здесь find справился мгновенно. Но лямбда больше чем в шестьдесят тысяч раз короче генома человека. Чтобы понять, выдержит ли поиск три миллиарда букв, нужно знать, как он устроен внутри. Напишем его сами.

Линейка

Задача называется поиском подстроки: дан текст длины $n$ и образец длины $m$, найти все позиции, где образец входит в текст. Первое решение приходит в голову само. Приложим образец к началу текста, как линейку, и сравним букву за буквой. Не совпало — сдвинем линейку на одну позицию и начнём сначала. Посчитаем заодно, сколько сравнений букв на это уйдёт.

На геноме лямбды линейка справляется неплохо: 1,36 сравнения на букву. Почти всегда первая же буква образца не совпадает, и линейка сразу едет дальше. Даже три миллиарда букв Python прошёл бы так за несколько минут. Но вторая половина вывода — другая история. В тексте из одних A образец AAA…AC совпадает почти до конца в каждой позиции, и лишь последняя буква его отвергает. Каждая позиция стоит $m$ сравнений, всего около $n \cdot m$: в десять раз длиннее образец — в десять раз дольше. Это худший случай, и для генома из трёх миллиардов букв и образца в тысячу букв он означает $3 \cdot 10^{12}$ сравнений — больше суток работы.

Текст из одних A кажется выдумкой, но похожие тексты пишет сама природа. На концах каждой хромосомы человека сидят теломеры — шесть букв TTAGGG, повторённые сотни и тысячи раз подряд. Повторы попроще и посложнее занимают около половины генома человека. Для наивного поиска такой текст — минное поле: на каждом повторе линейка проходит длинное совпадение и начинает заново с соседней позиции.

Текст — TTAGGG, повторённое 20 000 раз (120 000 букв). Образец — TTAGGG, повторённое 200 раз, и в конце TTAGGC: он почти совпадает с текстом, но не входит в него. Во сколько раз больше сравнений сделает наивный поиск, чем на тексте той же длины из одних случайных букв?

примерно вдвое примерно в двадцать раз больше чем в сто раз столько же: образец ведь не найдётся

Около 24 миллионов сравнений против 160 тысяч — в полтораста раз больше. В каждой шестой позиции линейка проходит больше тысячи совпадающих букв, прежде чем последняя C её остановит. Проверим это ниже, когда будет с чем сравнивать.

Где линейка теряет время, видно по позиции, в которой совпало 999 букв из тысячи. Мы только что прочитали 999 букв текста и точно знаем, какие они: те же, что в начале образца. А потом сдвигаем линейку на одну позицию и читаем их снова, как будто ничего не видели, — вся работа сравнений уходит в мусор. Чтобы её сберечь, придётся сначала кое-что выяснить о самом образце.

Что образец знает о себе

Возьмём образец абракадабра и представим, что линейка, приложенная к позиции $i$, совпала с текстом на первых десяти буквах, абракадабр, а на одиннадцатой сломалась. Какие сдвиги линейки имеют смысл? Мы знаем десять букв текста, ничего не перечитывая: это абракадабр. Сдвиг на одну позицию поставит начало образца а против б — бесполезно. Полезен только такой сдвиг, после которого начало образца совпадёт с концом уже прочитанного куска. Здесь подходит сдвиг на семь: тогда абр из начала образца ляжет на абр в конце прочитанного, и сравнение продолжится с четвёртой буквы образца. Текст при этом перечитывать не надо — про эти три буквы мы уже знаем, что они совпадают.

Значит, всё решает вопрос, в котором текста нет вовсе: каким самым длинным куском образец и начинается, и заканчивается? Такой кусок называют гранью строки: это начало строки, которое одновременно её конец, но не вся строка. У абракадабр самая длинная грань — абр, у всего слова абракадабра — абра, у абв граней нет. Длины самых длинных граней всех начал образца составляют таблицу — префикс-функцию $\pi$: $\pi[i]$ — длина самой длинной грани начала p[:i + 1].

Считать её перебором — брать каждое начало, пробовать все длины грани — долго, порядка $m^3$ действий. Но таблица строится сама из себя. Пусть мы знаем $k = \pi[i - 1]$: начало длины $k$ совпадает с концом p[:i]. Если следующая буква p[i] равна p[k], грань продлевается на одну букву, и $\pi[i] = k + 1$. Если не равна, нужна грань покороче, которая всё-таки продлится. Следующая по длине грань строки — это самая длинная грань её грани, то есть $\pi[k - 1]$: она уже есть в таблице. Пробуем её, потом грань грани грани — пока не продлится или пока $k$ не станет нулём.

Под каждой буквой — длина самой длинной грани слова до неё включительно. В конце абракадабры стоит 4: грань абра. У образца из теломеры на седьмой позиции начинается второй повтор TTAGGG, и грань растёт 1, 2, 3, 4, 5, пока последняя C не оборвёт её до нуля. Если нажать «Шаги», видно, как k откатывается в цикле while.

Ни шагу назад

Теперь поиск. Будем идти по тексту слева направо и помнить одно число $k$: сколько первых букв образца совпадает с концом прочитанного. Читаем очередную букву. Если она равна pattern[k], $k$ растёт. Если нет, образец сдвигается по таблице граней: $k$ превращается в $\pi[k - 1]$, и та же буква текста сравнивается снова, уже с другой буквой образца. Когда $k$ дорастает до $m$, образец найден. Указатель в тексте при этом никогда не идёт назад: каждая буква текста читается один раз, а все возвраты происходят внутри образца, по таблице. Это алгоритм Кнута — Морриса — Пратта, коротко КМП.

На случайном тексте оба поиска делают по 1,2–1,3 сравнения на букву. На теломере наивный делает двадцать четыре миллиона, а КМП — сто сорок тысяч, даже меньше, чем на случайном тексте. Ответ на ставку выше: в полтораста раз. Остаётся доказать, что КМП так же быстр на любом тексте.

Последняя строка вывода — встроенный in. На той же теломере он тратит доли миллисекунды: написан на C, и с версии 3.10 для длинных образцов использует ещё один линейный алгоритм — алгоритм «двух путей» Максима Крошмора и Доминика Перрена 1991 года. До 3.10 у in и find худший случай был квадратичным, как у нашей линейки.

В повседневной работе пишите in и find. Устройство линейного поиска пригодится там, где встроенные методы бессильны: в потоке, который приходит по букве и не помещается в память, в поиске сразу многих образцов, в списке чисел или событий вместо строки.

Число $k$ в КМП — это состояние: «сколько букв образца уже совпало». Новая буква переводит состояние в другое, и больше ничего алгоритм не помнит. Так устроен конечный автомат — о них будет целая глава. Автомат строится по одному образцу, а годится для любого текста; ниже его можно собрать для своего слова.

Откаты можно сосчитать заранее

Если алфавит маленький, как у ДНК, можно заранее для каждого состояния $k$ и каждой буквы записать в таблицу, в какое состояние попадёт автомат, — с учётом всех откатов. Тогда на каждую букву текста приходится ровно одно обращение к таблице, без всякого цикла while. Таблица занимает $(m + 1) \cdot |\Sigma|$ ячеек, где $|\Sigma|$ — размер алфавита: для ДНК это пустяк, для Юникода — нет. Так и работает поиск по регулярным выражениям в программах вроде grep: выражение превращается в автомат, а текст прогоняется через него буква за буквой.

Отпечатки: Рабин и Карп

КМП сравнивает буквы, но сравнивать можно и что-нибудь покрупнее. В главе 16 мы превращали строку в число многочленным хешем: умножить накопленное на основание, прибавить код буквы, взять остаток. Посчитаем такой хеш образца, а потом — хеш каждого окна текста длины $m$. Где хеши разные, строки точно разные. Где совпали — скорее всего, нашли, и это легко проверить сравнением. Хеш здесь работает как отпечаток пальца: короткий, но по нему почти всегда можно узнать владельца.

Подвох в том, что окон $n - m + 1$, и если считать хеш каждого заново, выйдет те же $n \cdot m$ действий, что у линейки. Но соседние окна почти одинаковые: при сдвиге на одну букву слева уходит одна буква и справа приходит одна. По схеме Горнера хеш окна $c_i c_{i+1} \ldots c_{i+m-1}$ равен $c_i B^{m-1} + c_{i+1} B^{m-2} + \ldots + c_{i+m-1}$ по модулю $p$, где $B$ — основание. Чтобы получить хеш следующего окна, достаточно вычесть вклад ушедшей буквы, умножить на $B$ и прибавить пришедшую:

$$h_{i+1} = \bigl( (h_i - c_i \cdot B^{m-1}) \cdot B + c_{i+m} \bigr) \bmod p.$$

Три арифметических действия на сдвиг, какой бы длины ни был образец. Хеш, который так обновляется, называют скользящим. Степень $B^{m-1}$ считается один раз заранее: встроенная pow(base, m - 1, mod) умеет возводить в степень сразу по модулю. Основание выберем случайное — почему, объясняла теорема о тайном основании из главы 16.

Пять мест EcoRI находятся при любом модуле: у равных строк хеши равны, и настоящее вхождение хеш не пропустит никогда. Разница — в ложных тревогах, когда хеши совпали, а строки нет. При модуле 7 хеш принимает всего семь значений, и тревогой оборачиваются тысячи окон. При модуле 101 — сотни, при 10 007 — то ни одной, то несколько десятков, а при $2^{61} - 1$ ни одной. Запустите ячейку несколько раз: основание случайное, и числа будут меняться. Ложных тревог порядка $n/p$: каждое окно попадает в хеш образца примерно с вероятностью $1/p$.

В формуле сдвига есть вычитание, и h - ord(...) * top бывает отрицательным. В Python остаток от деления на положительное число всегда неотрицателен, -5 % 7 равно 2, и формула работает как есть. В C и Java остаток от отрицательного числа отрицателен, -5 % 7 там равно −5, и к остатку приходится прибавлять модуль. Кто переносит код с хешами из Java в Python или обратно, рано или поздно об это спотыкается.

Алгоритм опубликовали Ричард Карп и Майкл Рабин в 1987 году. Оба — лауреаты премии Тьюринга, а Рабин — ещё и второе имя в тесте простоты Миллера — Рабина из прошлой главы. Их поиск тоже случайный, и в нём легко узнать оба вида случайных алгоритмов. Наша версия проверяет каждое совпадение хешей, поэтому ответ всегда верный, а случайным бывает только время: при неудачном основании ложных тревог больше, и поиск медленнее. Это алгоритм Лас-Вегаса. Если проверку убрать, поиск станет быстрее на каждой тревоге, но изредка будет ошибаться — алгоритм Монте-Карло. По теореме о тайном основании вероятность, что одно конкретное окно даст ложную тревогу, не больше $(m - 1)/p$. Для лямбды, образца из шести букв и $p = 2^{61} - 1$ ошибка во всём поиске случится в среднем не чаще, чем раз на девять триллионов запусков.

КМП гарантирует линейное время без всякой вероятности, и всё же у отпечатков есть своё дело: они умеют то, чего не умеет автомат одного образца. Если образцов тысяча, но все одной длины, сложите их хеши в множество, и каждое окно текста будет стоить одну проверку h in hashes, сколько бы образцов ни было. А если сравнить отпечатки всех кусков одного текста с отпечатками всех кусков другого, получится антиплагиат — к нему мы придём во второй половине главы.

Каталог ножниц: бор

Ферментов рестрикции известно множество, и у разных ферментов мотивы разной длины: у AluI и HaeIII по четыре буквы, у EcoRI шесть, у NotI восемь. Отпечатки Рабина — Карпа сравнивают только окна одной длины, поэтому для каталога понадобится другая идея. Сложим все мотивы в одно дерево. Из корня выходят стрелки с буквами, по которым начинаются мотивы; из каждого следующего узла — стрелки с буквами, которыми мотив может продолжиться. Мотивы с общим началом делят общий путь: GATC и GATATC расходятся только на четвёртой букве. Узел, в котором кончается мотив, помечен именем фермента.

Такое дерево называют бором. В 1959 году его описал Рене де ла Брианде, а в 1960-м Эдвард Фредкин назвал trie — по середине слова retrieval, «выборка». Русское слово появилось в первом русском переводе «Искусства программирования» Кнута, и его обычно объясняют так же — серединой слова «выборка». Бор в Python удобно строить из словарей: узел — словарь «буква → следующий узел», а метка конца — особый ключ.

Метод setdefault(ch, {}) возвращает значение по ключу, а если ключа нет — сперва кладёт туда пустой словарь: так путь по бору прокладывается без лишних проверок. Четырнадцать ферментов просмотрены за один проход по геному, и на каждую букву пришлось меньше двух шагов по бору. Четырёхбуквенные мотивы встречаются в лямбде больше сотни раз — для случайного текста ожидалось бы около $48\,502 / 4^4 \approx 190$, — а восьмибуквенный NotI не встречается ни разу. Поэтому NotI и любят генетики: он режет большой геном на немногие длинные куски.

Бор плюс префикс-функция: Ахо — Корасик

Наш проход по бору из каждой позиции начинает заново, как линейка, и в худшем случае стоит $n \cdot L$ шагов, где $L$ — длина самого длинного мотива. Лекарство то же, что у КМП: заранее посчитать для каждого узла бора, куда откатываться при несовпадении, — узел самой длинной грани, только теперь грань ищется среди всех мотивов сразу. Получается автомат, который проходит текст один раз без возвратов и находит все вхождения всех мотивов за $O(n + \text{длина мотивов} + \text{число находок})$. Его придумали Альфред Ахо и Маргарет Корасик в Bell Labs в 1975 году, и на нём работала утилита fgrep, которая ищет в файлах сразу много слов.

Тот же бор живёт в каждом телефоне. Вы набираете «нат», а клавиатура предлагает «наташа», — значит, где-то есть словарь, который по началу слова быстро выдаёт все слова с этим началом. В отсортированном списке или в хеш-таблице для этого пришлось бы перебирать слова; в бору достаточно спуститься по трём буквам приставки — и всё нужное лежит в одном поддереве. Соберём бор из всех 448 тысяч слов «Войны и мира» и будем считать в узлах, сколько раз слово встретилось: подсказки разумно упорядочить по частоте. Узел теперь удобнее сделать классом, как в главе 17.

В пятидесяти одной тысяче разных слов 437 тысяч букв, а узлов в бору втрое меньше — 132 тысячи: общие начала хранятся один раз. Запрос стоит столько шагов, сколько букв в приставке, плюс обход поддерева, а размер словаря на спуск не влияет. Подсказки получились верные, но бесхитростные: на «бор» роман отвечает Борисом и Бородинским сражением, а на «войн» — пятью формами одного слова. Клавиатуры в телефонах учитывают ещё и предыдущее слово, как цепочки слов из главы 8, и ваши собственные привычки. Попробуйте сами.

В главе 48 бор вернётся как часть поисковика по нашим учебникам. А пока лаборатория закрывается, и мы переходим в учительскую.

Комиссия. Три сочинения

Учительница литературы принесла три сочинения на одну тему — «Дуб в „Войне и мире“». Их писали Аня, Боря и Вера. Сочинения Ани и Бори кажутся ей подозрительно похожими, но Боря говорит, что это совпадение: тема одна, и роман один. Комиссии нужна мера сходства, которую можно посчитать, а не почувствовать.

Первым на ум приходит diff из главы 22: наибольшая общая подпоследовательность слов. Она выдерживает вставки и замены, но плохо переносит перестановки: Боря передвинул фразу «Дуб в романе — …» из начала в середину, а общая подпоследовательность может взять её только в одном из двух мест. К тому же таблица стоит $n \cdot m$ на каждую пару, а пар в школе с тысячей сочинений полмиллиона. Нужна мера, которой порядок кусков безразличен и которая считается быстро.

Разрежем каждый текст на шинглы — кусочки из $k$ слов подряд, внахлёст, как черепица на крыше: отсюда и английское shingle. Текст из $N$ слов даёт $N - k + 1$ шинглов. Сходство двух текстов — доля общих шинглов среди всех: $J(A, B) = \frac{|A \cap B|}{|A \cup B|}$. Эту меру ввёл в 1901 году швейцарский ботаник Поль Жаккар, который сравнивал так флору разных участков Альп и Юры: сколько видов растений у двух участков общие. Её называют коэффициентом Жаккара. Для документов шинглы и эту меру предложил Андрей Бродер в 1997 году: поисковик AltaVista искал так почти одинаковые страницы в интернете.

Функция normalize — это words из главы 7 с одной добавкой: буква «ё» заменяется на «е». Иначе «узнаёт» и «узнает» оказались бы разными словами, а в издании Толстого, по которому мы будем сверять дальше, «ё» почти нигде не пишется. При $k = 1$ шинглы совпадают со словами, и даже независимые сочинения Ани и Веры делят каждое восьмое: «дуб», «князь», «андрей», «толстой». Уже при $k = 3$ совпадения между самостоятельными работами исчезают, а у Ани с Борей держатся: при $k = 4$ общих шинглов 44, больше трети всех. Совпадение одного слова случайно, совпадение четырёх слов подряд сорок четыре раза — нет. Переставленная фраза тоже дала общие шинглы: порядок кусков мере безразличен.

Просеивание

Три сочинения можно сравнить попарно. Но комиссия хочет большего: сверять каждую новую работу со всеми прошлыми работами школы — и с самим романом, откуда тоже можно списать. В «Войне и мире» почти 450 тысяч шинглов, и в архиве за десять лет — ещё миллионы. Хранить их все дорого. Хочется хранить малую выборку — отпечатки документа, — но так, чтобы ни одно заметное заимствование не потерялось.

Очевидные способы не годятся. Брать каждый четвёртый шингл нельзя: стоит Боре вставить в начало одно слово, и все номера сдвинутся, а в списанном куске выберутся другие шинглы, чем у Ани. Можно выбирать шинглы по самому хешу — например, только те, чей хеш делится на четыре. Сдвиги такой выбор переживает, но гарантии не даёт: в длинном общем куске может не найтись ни одного хеша, кратного четырём. Решение нашли в 2003 году Сол Шлаймер, Дэниел Уилкерсон и Алекс Эйкен. Посчитаем хеши всех шинглов по порядку и пройдём по ним окном ширины $w$. В каждом окне запишем в отпечатки самый маленький хеш. Соседние окна часто выбирают один и тот же минимум, поэтому отпечатков выходит немного. Этот способ назвали просеиванием — winnowing, как отделяют зерно от мякины.

Заимствование короче этого порога может и проскочить, но беды в этом нет: совпадения из трёх-четырёх слов бывают случайными. Долю отпечатков можно оценить заранее. Если хеши ведут себя как случайные числа, при окне $w$ в отпечатки попадает в среднем около $\frac{2}{w + 1}$ всех шинглов — при $w = 4$ это 40 процентов, при $w = 50$ — четыре. Проверим всё сразу на задаче посерьёзнее. Четвёртый ученик, Гоша, сдал описание дуба. Найдём, откуда оно.

Почти полмиллиона слов романа превратились примерно в 179 тысяч отпечатков — сорок процентов, как и обещано. Индекс строится за доли секунды, а поиск по нему — это несколько обращений к словарю: хеш-таблица снова делает всю работу. Гоша переставил слова, выбросил половину фразы и даже написал «берёз» через «ё», но около десятка отпечатков совпали и указали точно: второй том, третья часть, весна 1809 года, князь Андрей едет в рязанские имения.

Хеши здесь считает встроенный hash, а у него, как мы видели в главе 16, есть соль. Для одного запуска это неважно: индекс и запрос считаются одной функцией. А вот хранить такой индекс на диске нельзя — после перезапуска соль будет другой. Антиплагиат, который копит архив годами, берёт хеш-функцию без соли, например многочленный хеш с фиксированным основанием.

Это предупреждение относится и к нашей комиссии. Если бы Вера взяла описание дуба в кавычки и сослалась на Толстого, отпечатки нашли бы его точно так же: цитата — тоже общий кусок. Отличить её от списывания может только человек, который прочтёт оба текста.

Снова лаборатория: все суффиксы сразу

Вернёмся к генетикам с последним вопросом. До сих пор образец был известен заранее, а текст читался один раз. В лаборатории всё наоборот: геном один и не меняется, а образцы приходят каждый день сотнями. Значит, выгодно один раз потрудиться над текстом и построить указатель, по которому любой образец находится быстро, — как предметный указатель в конце книги.

Каждое вхождение образца — это начало какого-то суффикса текста, его хвоста с некоторой позиции до конца. Выпишем все $n$ суффиксов и отсортируем их по алфавиту, а храним только номера позиций, с которых они начинаются. Это суффиксный массив. Все суффиксы, которые начинаются с образца, стоят в нём подряд, и этот отрезок находится двоичным поиском из главы 20 — за $O(m \log n)$, сколько бы образцов ни пришло. А ещё в нём видны повторы: если кусок текста встречается дважды, два суффикса начинаются с него и при сортировке окажутся соседями. Самый длинный повтор — самое длинное общее начало соседей в массиве.

Отсортировать суффиксы в лоб, sorted(range(n), key=lambda i: s[i:]), можно, но каждый ключ — копия хвоста: для генома лямбды это миллиард с лишним букв в памяти. Удобнее приём удвоения. Сначала упорядочим суффиксы по первой букве и дадим каждому ранг — номер его группы. Потом по первым двум буквам: это пара рангов «первая буква, буква через одну позицию». Потом по четырём: пара рангов «первые две буквы, следующие две». Каждый раз длина удваивается, и через $\log n$ таких сортировок порядок становится полным.

С Python 3.10 функции bisect принимают key: здесь он вырезает из каждого суффикса первые шесть букв, и поиск сравнивает с образцом только их. Пять мест EcoRI нашлись снова — теперь за два двоичных поиска по готовому массиву.

А повторы короткие: 12 букв у φX174, по 15 у митохондрии и лямбды. Много это или мало, подскажет парадокс дней рождения из главы 16. В случайном тексте из $n$ букв около $n^2/2$ пар окон длины $L$, и каждая пара совпадает с вероятностью $4^{-L}$. Совпадений становится около одного, когда $4^L \approx n^2/2$, то есть при $L \approx 2\log_4 n$. Для φX174 это 12,4, для митохондрии 14, для лямбды 15,6. В этих геномах повторы не длиннее случайных: геном фага экономен, лишнего в нём нет.

У человека всё иначе. Около десятой части его генома — больше миллиона копий одного куска длиной около трёхсот букв. Кусок назвали Alu: впервые его разрезали ферментом AluI из нашего каталога. А возле центромер, перетяжек хромосом, повторы тянутся на миллионы букв. Вот почему черновик 2001 года собрали, а последние проценты генома пришлось ждать до 2022-го: обрывок длиной в сотни букв из такого места подходит в тысячу мест сразу. Дочитать геном помогли новые приборы — они читают куски по десяткам тысяч букв.

Задачи

Четыре задачи: два линейных поиска, подсказки клавиатуры и повторы. В каждой заготовка уже даёт верные ответы, но работает медленно, и тесты с большими входами её не пропустят.

Напишите prefix_function(p) — список $\pi$ для последовательности p, и find_all(text, pattern) — список всех позиций, с которых pattern входит в text, по возрастанию, включая пересекающиеся вхождения. Образец не пустой. Функции должны работать не только со строками, но и со списками: тесты ищут, например, мотив «Братца Якова» в списке нот — номеров клавиш синтезатора. Поэтому строковые find и in здесь не помогут. В тестах есть последовательности по двести–триста тысяч элементов, и на всё дано две секунды.

Заготовка верна, но медленна: prefix_function перебирает все длины грани для каждой позиции, а find_all — линейка, которая на списке из нулей с единицей в середине сравнивает по двадцать тысяч элементов в каждой позиции. Перенесите prefix_function из раздела о гранях: в ней нет ничего строкового, индексы и != одинаково работают для строк и списков.

В find_all держите одно число k — сколько элементов образца совпало с концом прочитанного. Для каждого элемента текста: пока k > 0 и элемент не равен pattern[k], откатывайте k = pi[k - 1]; если равен — k += 1.

Найдя вхождение (k == len(pattern)), не сбрасывайте k в ноль: следующее вхождение может пересекаться с этим, как aa в aaaa. Откатитесь по грани: k = pi[k - 1].

Обе функции линейны по теореме о монетках: k растёт не больше чем на единицу за шаг, а каждый откат его уменьшает. КМП ничего не знает о буквах — ему нужно только сравнение на равенство. Поэтому он ищет мотив в нотах, последовательность в логе событий или образец в потоке, который приходит по одному элементу и в память не помещается.

Напишите window_hashes(s, k, base, mod) — список многочленных хешей всех окон длины k строки s по порядку. Хеш окна считается по схеме Горнера, как poly_hash в главе: начать с нуля, на каждой букве умножить на base, прибавить ord(буквы), взять остаток от деления на mod. Если окно длиннее строки, ответ — пустой список. Потом напишите rk_find(text, pattern, base, mod) — все позиции вхождений образца. Тесты дают строку в миллион букв с окном в десять тысяч и три секунды, а rk_find проверяют с модулем 7, при котором ложные тревоги на каждом шагу.

В заготовке две беды. window_hashes считает хеш каждого окна заново — это $n \cdot k$ действий, десять миллиардов на большом тесте. А rk_find верит каждому совпадению хешей.

Посчитайте хеш первого окна по Горнеру, а дальше сдвигайте: h = ((h - ord(s[i - 1]) * top) * base + ord(s[i + k - 1])) % mod, где top = pow(base, k - 1, mod) — вес первой буквы окна, посчитанный один раз.

В rk_find совпадение хешей — только повод проверить: сравните срез text[i:i + m] с образцом.

Сдвиг окна стоит три действия, и миллион окон считается за доли секунды, какой бы длины ни было окно. Проверка срезом делает поиск алгоритмом Лас-Вегаса: ответ всегда верный, а время зависит от удачи с хешем. При модуле 7 проверок много, при $2^{61} - 1$ — практически только настоящие находки. Проверка if k > len(s) не лишняя: без неё s[:k] молча вернёт всю строку, и короткая строка получит хеш окна, которого нет.

Напишите класс Trie с тремя методами. insert(word) добавляет одно употребление слова. count(word) — сколько раз слово вставляли (ноль, если ни разу; начало слова словом не считается). complete(prefix, k) — не больше k слов, которые начинаются с prefix, самые частые первыми, при равной частоте — по алфавиту; само слово prefix, если оно вставлялось, тоже годится. Тесты загружают все 448 тысяч слов «Войны и мира» и задают двадцать тысяч запросов — на запросы дано три секунды.

Заготовка на каждый запрос перебирает все пятьдесят тысяч разных слов. Двадцать тысяч запросов — миллиард проверок startswith. Бор спускается по буквам приставки и смотрит только в нужное поддерево.

Узел — объект с полями children (словарь «буква → узел») и count. Спуск по приставке пригодится и в count, и в complete: вынесите его в отдельный метод, который возвращает узел или None.

В complete обойдите поддерево стеком, как в главе, собирая пары (-count, word). Отсортированные по возрастанию, такие пары сами выстраиваются в нужном порядке: сначала большие частоты, при равенстве — по алфавиту.

Запрос стоит длину приставки плюс размер поддерева. Для приставок из четырёх-шести букв поддерево — десятки узлов, и двадцать тысяч запросов укладываются в доли секунды. Для однобуквенной приставки поддерево огромно, поэтому клавиатуры хранят в каждом узле готовый список лучших продолжений и обновляют его при вставке. Можно обойтись и без бора — отсортированным списком слов: все слова с приставкой стоят в нём подряд, и двоичный поиск из главы 20 находит этот отрезок.

Напишите longest_repeat(s) — самый длинный кусок строки, который встречается в ней хотя бы дважды; вхождения могут пересекаться, как ana в banana. Если таких кусков несколько, верните любой; если повторов нет, — пустую строку. Тесты берут геном φX174, случайную ДНК в сто тысяч букв с вставленным повтором — и строки, которые сплошь состоят из повторов: теломеру и одни A. На геном дано четыре секунды, на остальные большие строки — по пять.

Если кусок длины $L$ повторяется, то повторяется и его начало длины $L - 1$. Значит, ответ на вопрос «есть ли повтор длины $L$» сначала «да», потом «нет», и границу можно найти двоичным поиском по $L$ — за $\log n$ проверок вместо $n$.

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

Суффиксный массив из главы тоже годится, но осторожно: общие начала соседей, посчитанные сравнением букв, на строке из одних A стоят квадрат. Если идёте этим путём, общие начала считают за линейное время алгоритмом Касаи — найдите его сами.

Двоичный поиск по длине делает около семнадцати проверок для ста тысяч букв, каждая — один проход скользящим хешем, всего $O(n \log n)$. Заготовка начинает с самых длинных кусков и для случайной строки тратит на них порядка $n^3$ действий. Подвох теста с одними A в другом: там почти всё — повторы, и решения, которые сравнивают куски буква за буквой без хешей, становятся квадратичными. Хеш сравнивает кусок любой длины за одно действие, а срез для проверки здесь нужен лишь один раз на проверку.

Куда дальше

КМП, отпечатки, бор и суффиксный массив молчаливо полагаются на одно: если буквы выглядят одинаково, то и символы строки одинаковы. Проверим это на том же романе.

В издании Толстого, которое лежит в песочнице, ударения расставлены над словами, где без них легко ошибиться, и «сто́ит» в значении цены встречается 9 раз. Поиск «стоит» их не находит: слово с ударением на один символ длиннее, хотя букв в нём столько же. Ударение — отдельный невидимый символ, который приклеивается к предыдущей букве. С «й» ещё хуже: на экране две строки выглядят одинаково, но в одной «й» — один символ, а в другой — два, «и» и значок краткой над ней. Сравнение говорит False, и ни КМП, ни бор, ни in одну «й» в другой не найдут.

Последняя строка вывода показывает, из чего строки сделаны. Метод encode превращает строку в байты — то, что лежит в памяти и в файле. Слово из трёх букв занимает шесть байт в одной записи и восемь в другой, а латинская буква заняла бы один. Целую главу мы искали буквы, ни разу не спросив, что такое буква внутри машины. Почему одна буква — это два числа, а другая — одно? Что будет, если прочитать эти числа не так, как их записали? Этим займётся следующая глава, первая в части о том, как устроена сама машина.