Всем привет!

В этот раз я хотел бы написать про алгоритм Ахо-Корасик. Структура эта очень хорошо описана и многие о ней уже, должно быть, знают. Однако, я всё же постараюсь описать некоторые применения, которые не столь известны.

Для начала о самой структуре. Данный алгоритм был предложен Альфредом Ахо и Маргарет Корасик. Изначальное его предназначение — оптимальный поиск строк из какого-то набора в тексте. Т. е., допустим нам даны строки {"a", "abba", "acb"} и дан текст, скажем, "abacabba". С помощью Ахо-Корасик мы сможем для каждой строки из набора сказать, входит ли она в текст и, например, указать первое вхождение в строку за время , где |T| — суммарная длина текста, а |S| — суммарная длина шаблонов. Но на самом деле это капля в море по сравнению с тем, что позволяет делать этот алгоритм.

Чтобы понять, как все это следует делать — обратимся к префикс-функции и алгоритму КМП. Напомню, префикс-функцией называется массив π[i] = max(k): s[0..k) = s(i - k..i], то есть, π[i] — длина наибольшего собственного (не совпадающего со всей строкой) суффикса, который совпадает с префиксом для подстроки [0..i]. Рассмотрим простейший алгоритм её получения. Пусть у нас уже посчитаны все значения префикс-функции на отрезке от 0 до i - 1. В таком случае мы можем несколько раз "попрыгать" по позициями π[i - 1], π[π[i - 1] - 1], π[π[π[i - 1] - 1] - 1]... и так далее. Пускай в данный момент после ряда прыжков мы находимся в позиции t. Если s[t + 1] = s[i] и при этом t максимально возможное, то тогда и только тогда π[i] = t + 1. Если считать префикс-функцию описанным выше способом, мы получим её за . Действительно, на каждом шагу мы несколько раз сужаем область поиска, а в конце расширяем её всего лишь на один элемент. Расширений будет не больше n, а сужений, очевидно, не может быть больше, чем расширений. Однако, в процессе пересчёта префикс функции для конкретного индекса мы можем честно пройти все i - 1 символов до него, что может сильно усложнить жизнь в некоторых случаях.

Позже будет показано, как улучшить оценку подсчёта в отдельно взятой позиции до строгой . Пока же давайте построим автомат^[1], который позволит нам знать, чему равна длина наибольшего суффикса некоторого текста T, равного префиксу строки S и кроме этого добавлять символы к концу текста, быстро пересчитывая эту информацию. Итак, пытаемся "скормить" текст автомату, т.е., пройти по символам в автомате, которые соответствуют строке. Если нам это удаётся, то всё хорошо. Иначе же мы переходим по суффиксной ссылке, пока не обнаружим требуемый переход и продолжаем. Суффиксной ссылкой здесь и далее будем называть некий указатель на состояние, соответствующему самому длинному собственному суффиксу строк, которые принимает текущее состояние (т.е., пройдя по символам которых мы попадём в состояние), который имеет собственное состояние. Легко видеть, что в данном автомате суффиксной ссылкой будем выступать значение префикс-функции. И вновь мы можем за целиком пропустить строку через автомат из тех же соображений, которые были указаны в прошлом абзаце.

Посмотрим теперь, как улучшить до константы время одного такого перехода. Давайте сделаем автомат полным, т.е., чтобы из каждого состояния были переходы по каждой букве из алфавита. Тогда, очевидно, переход будет требовать всего одно действие. Но как это сделать? Очень просто! Допустим, у нас посчитаны переходы в автомате для всех k < i. Легко заметить, что всё, что нам нужно, чтобы получить корректные переходы из состояние i — скопировать их из состояния, в которое мы бы перешли по суфф ссылке и затем заменить один единственный переход — по букве s[i + 1] в состояние i + 1. Суфф ссылку же для этого состояния можно получить, перейдя по символу s[i] из суффиксной ссылки состояние i - 1. Как можно видеть, всё считается за . Или, что точнее — за , где — размер алфавита.

Наконец, вернёмся к задаче о поиске нескольких строк. Кому-то может показаться, что это только начало долгого и нудного описания алгоритма, но на самом деле алгоритм уже описан и если вам понятно всё, что изложено выше, вы поймёте и то, что я напишу сейчас.

Итак, обобщим автомат, полученный ранее (назовём его префикс-автомат). Объединим наш набор строк-шаблонов в префиксное дерево. Теперь сделаем из него автомат — в каждой вершине бора будет храниться суффиксная ссылка на состояние, соответствующее наибольшему суффиксу строки данной вершины, который присутствует в дереве. Можно видеть, что абсолютно аналогично тому, как это делается в префикс-автомате мы теперь, пропуская текст через новый автомат, в любой момент можем поддерживать состояние, которое соответствует наибольшему суффиксу пропускаемой строки. Осталось только научиться считать эти ссылки.

Я предлагаю делать это таким образом: запустить обход в ширину из корня. Пусть в данный момент мы находимся в состоянии v. Тогда "протолкнём" суффиксные ссылки всем его потомкам в боре по тому же принципу, как это делается в префикс-автомате. Такое решение корректно, т.к. если мы находимся в вершине v при обходе в ширину, у нас уже посчитан ответ для всех вершин, расстояние которых до корня (т.е. длина соответствующих им подстрок) меньше, чем у нашей, а именно такое требование мы раньше предъявляли при получении суфф ссылок в префикс-автомате. Есть также некоторые другие способы, использующие "ленивую" динамику, их можно видеть, например, на e-maxx.ru.

[1] В данном случае будем считать автоматом некий ориентированный граф, над дугами которого написаны символы. Вершины в нём будем называть состояниями, а дуги — переходами. Пройдя какой-то путь по этому графу, мы окажемся в состоянии, которое соответствует строке, которую мы бы получили, если бы записывали символы, по которым мы "переходили". Это не совсем корректно, но такого определения достаточно для того, что мы собираемся делать. В данном случае автоматом будет сама строка. Таким образом, из состояния i будет переход по букве s[i + 1] в состояние i + 1.

Реализация основных функций: http://ideone.com/J1XjX6
Альтернативная версия: http://ideone.com/0cMjZJ
Легко проглядывается схожесть с префикс-функцией.

Рекомендуемые задачи:

1. UVA — I love strings!!
2. Timus 1269 — Антимат
3. Timus 1158 — Censored!
4. MIPT El Judge — Вопль
5. SPOJ — Morse

Позже я хотел бы рассказать о некоторых более продвинутых трюках с этой структурой, а также об одной интересной родственной структуре. Так что stay tuned :)

P.S. Если вам что-то непонятно или кажется слишком сложно описанным, хотя можно было бы легче — пожалуйста, не стесняйтесь написать об этом в комментариях. Я стараюсь сделать статью максимально понятной, но я не могу гарантировать, что мне это всегда удаётся :)