E107. 알고리즘 Ахо-Корасик

Источник: e-maxx.ru/algo, страница PDF 335.

Пусть дан набор строк в алфавите размера

суммарной длины

. 알고리즘 Ахо-Корасик строит для этого набора

строк структуру данных "бор", а затем по этому бору строит автомат, всё за

времени и

памяти. Полученный автомат уже может использоваться в различных 문제х, простейшая из которых — это нахождение всех вхождений каждой строки из данного набора в некоторый текст за линейное время. Данный 알고리즘 был предложен канадским учёным Альфредом Ахо (Alfred Vaino Aho) и учёным Маргарет Корасик (Margaret John Corasick) в 1975 г.

Бор. Построение бора

Формально, бор — это 트리 с корнем в некоторой вершине

, причём каждое edge 트리 подписано

некоторой буквой. Если мы рассмотрим список рёбер, 출력ящих из данной вершины (кроме ребра, ведущего в предка), то все рёбра должны иметь разные метки. Рассмотрим в боре любой путь из корня; выпишем подряд метки рёбер этого пути. В результате мы получим некоторую строку, которая соответствует этому пути. Если же мы рассмотрим любую вершину бора, то ей поставим в соответствие строку, соответствующую пути из корня до этой вершины.

Каждая vertex бора также имеет флаг

, который равен

, если в этой вершине оканчивается какая-либо

문자열 из данного набора. Соответственно, построить бор по данному набору строк — значит построить такой бор, что каждой

-

вершине будет соответствовать какая-либо 문자열 из набора, и, наоборот, каждой строке из набора будет

соответствовать какая-то

-vertex. Опишем теперь, как построить бор по заданному набору строк за линейное время относительно их суммарной длины. Введём структуру, соответствующую vertexм бора:

struct vertex {

int next[K];

bool leaf;

};

vertex t[NMAX+1];

int sz;

Т.е. мы будем хранить бор в виде 배열а

(количество elementов в 배열е - это sz) структур

.

Структура

содержит флаг

, и рёбра в виде 배열а

, где

— указатель на вершину,

в которую ведёт edge по символу

, или

, если такого ребра нет. Вначале бор состоит только из одной вершины — корня (договоримся, что корень всегда имеет в 배열е

индекс

). Поэтому инициализация бора такова:

memset (t[0].next, 255, sizeof t[0].next);

sz = 1;

Теперь реализуем функцию, которая будет добавлять в бор заданную строку . 구현 крайне проста: мы встаём в корень бора, смотрим, есть ли из корня переход по букве

: если переход есть, то просто переходим

по нему в другую вершину, иначе создаём новую вершину и добавляем переход в эту вершину по букве

. Затем

мы, стоя в какой-то вершине, повторяем процесс для буквы

, и т.д. После окончания процесса помечаем

последнюю посещённую вершину флагом

.

void add_string (const string & s) {

int v = 0;

for (size_t i=0; i<s.length(); ++i) {

char c = s[i]-'a'; // в зависимости от алфавита

if (t[v].next[c] == -1) {

memset (t[sz].next, 255, sizeof t[sz].next);

t[v].next[c] = sz++;

}

v = t[v].next[c];

}

t[v].leaf = true;

} Линейное 실행 시간, а также линейное количество вершин в боре очевидны. Поскольку на каждую

вершину приходится

памяти, то использование памяти есть

.

Потребление памяти можно уменьшить до линейного (

), но за счёт увеличения асимптотики работы

до

. Для этого достаточно хранить переходы

не 배열ом, а отображением

.

Построение автомата

Пусть мы построили бор для заданного набора строк. Посмотрим на него теперь немного с другой стороны. Если мы рассмотрим любую вершину, то 문자열, которая соответствует ей, является префиксом одной или нескольких строк из набора; т.е. каждую вершину бора можно понимать как позицию в одной или нескольких 문자열х из набора. Фактически, вершины бора можно понимать как состояния конечного детерминированного автомата. Находясь в каком-либо состоянии, мы под воздействием какой-то 입력ной буквы переходим в другое состояние — т.е. в другую позицию в наборе строк. На예제, если в боре находится только 문자열

и

мы стоим в состоянии

(которому соответствует 문자열

), то под воздействием буквы

мы перейдём в

состояние

. Т.е. мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние.

Более строго, пусть мы находимся в состоянии

, которому соответствует некоторая 문자열

, и хотим выполнить

переход по символу

. Если в боре из вершины

есть переход по букве

, то мы просто переходим по этому ребру

и попадаем в вершину, которой соответствует 문자열

. Если же такого ребра нет, то мы должны find

состояние, соответствующее наидлиннейшему собственному суффиксу строки

(наидлиннейшему из имеющихся в

боре), и попытаться выполнить переход по букве

из него.

На예제, пусть бор построен по 문자열м

и

, и мы под воздействием строки

перешли в

некоторое состояние, являющееся листом. Тогда под воздействием буквы

мы вынуждены перейти в

состояние, соответствующее строке

, и только оттуда выполнить переход по букве

.

Суффиксная ссылка для каждой вершины

— это vertex, в которой оканчивается

наидлиннейший собственный суффикс строки, соответствующей вершине

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

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

, то мы можем перейти в предка

текущей вершины (пусть

— буква, по которой из

есть переход в

), затем перейти по его суффиксной ссылке,

а затем из неё выполнить переход в автомате по букве

. Таким образом, 문제 нахождения перехода свелась к задаче нахождения суффиксной ссылки, а 문제 нахождения суффиксной ссылки — к задаче нахождения суффиксной ссылки и перехода, но уже для более близких к корню вершин. Мы получили рекурсивную зависимость, но не бесконечную, и, более того, разрешить которую можно за линейное время. Перейдём теперь к реализации. Заметим, что нам теперь понадобится для каждой вершины хранить её предка

,

а также символ

, по которому из предка есть переход в нашу вершину. Также в каждой вершине будем

хранить

— суффиксная ссылка (или

, если она ещё не вычислена), и 배열

— переходы

в автомате по каждому из символов (опять же, если element 배열а равен , то он ещё не вычислен). Приведём теперь полную реализацию всех необходимых функций:

struct vertex {

int next[K];

bool leaf;

int p;

char pch;

int link;

int go[K];

};

vertex t[NMAX+1];

int sz;

void init() {

t[0].p = t[0].link = -1;

memset (t[0].next, 255, sizeof t[0].next);

memset (t[0].go, 255, sizeof t[0].go);

sz = 1;

}

void add_string (const string & s) {

int v = 0;

for (size_t i=0; i<s.length(); ++i) {

char c = s[i]-'a';

if (t[v].next[c] == -1) {

memset (t[sz].next, 255, sizeof t[sz].next);

memset (t[sz].go, 255, sizeof t[sz].go);

t[sz].link = -1;

t[sz].p = v;

t[sz].pch = c;

t[v].next[c] = sz++;

}

v = t[v].next[c];

}

t[v].leaf = true;

}

int go (int v, char c);

int get_link (int v) {

if (t[v].link == -1)

if (v == 0 || t[v].p == 0)

t[v].link = 0;

else

t[v].link = go (get_link (t[v].p), t[v].pch);

return t[v].link;

}

int go (int v, char c) {

if (t[v].go[c] == -1)

if (t[v].next[c] != -1)

t[v].go[c] = t[v].next[c];

else

t[v].go[c] = v==0 ? 0 : go (get_link (v), c);

return t[v].go[c];

} Нетрудно понять, что, за счёт запоминания найденных суффиксных ссылок и переходов, суммарное время нахождения всех суффиксных ссылок и переходов будет линейным.

Applications

Поиск всех строк из заданного набора в тексте

Дан набор строк, и дан текст. it is required вывести все вхождения всех строк из набора в данный текст за

время

, где

— длина текста,

— размер ответа. Построим по данному набору строк бор. Будем теперь обрабатывать текст по одной букве, перемещаясь соответствующим образом по дереву, фактически — по состояниям автомата. Изначально мы находимся в корне

дерева. Пусть мы на очередном шаге мы находимся в состоянии

, и очередная буква текста

. Тогда следует

переходить в состояние

, тем самым либо увеличивая на

длину текущей совпадающей подстроки,

либо уменьшая её, проходя по суффиксной ссылке.

Как теперь узнать по текущему состоянию

, имеется ли совпадение с какими-то 문자열ми из набора? Во-первых,

понятно, что если мы стоим в помеченной вершине (

), то имеется совпадение с тем образцом, который

в боре оканчивается в вершине

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

— когда набор строк — это

, а текст — это

. Таким образом, если в каждой помеченной вершине хранить номер образца, оканчивающегося в ней (или список номеров, если допускаются повторяющиеся образцы), то мы можем для текущего состояния за

find номера

всех образцов, для которых достигнуто совпадение, просто пройдя по суффиксным ссылкам от текущей вершины до корня. Однако это недостаточно эффективное 해법, поскольку в сумме Asymptotic complexity получится . Однако можно заметить, что движение по суффиксным ссылкам можно соптимизировать, предварительно посчитав для каждой вершины ближайшую к ней помеченную вершину, достижимую по суффиксным ссылкам (это называется "функцией 출력а"). Эту величину можно считать ленивой динамикой за линейное время. Тогда для

текущей вершины мы сможем за

находить следующую в суффиксном пути помеченную вершину, т.е. следующее совпадение. Тем самым, на каждое совпадение будет тратиться

действий, и в сумме

получится Asymptotic complexity

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

по суффиксным ссылкам. Эта величина может быть посчитана за

в сумме, и тогда для текущего состояния

мы сможем за

find количество вхождений всех образцов в текст, оканчивающихся в текущей позиции. Тем самым, 문제 нахождения суммарного количества вхождений может быть решена нами за .

Нахождение лексико그래프ически наименьшей строки данной длины,

не содержащей ни один из данных образцов

Дан набор образцов, и дана длина

. it is required find строку длины

, не содержащую ни один из образцов, и из

всех таких строк вывести лексико그래프ически наименьшую. Построим по данному набору строк бор. Вспомним теперь, что те вершины, из которых по суффиксным ссылкам

можно достичь помеченных вершин (а такие вершины можно find за

, на예제, ленивой динамикой),

можно воспринимать как вхождение какой-либо строки из набора в заданный текст. Поскольку в данной задаче нам необходимо избегать вхождений, то это можно понимать как то, что в такие вершины нам заходить нельзя. С другой стороны, во все остальные вершины мы заходить можем. Таким образом, мы удаляем из автомата все "плохие" вершины, а в оставшемся 그래프е автомата it is required find лексико그래프ически наименьший путь длины .

Эту задачу уже можно решить за

, на예제, поиском в глубину.

Нахождение кратчайшей строки, содержащей

вхождения одновременно всех образцов

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

в состоянии

, it is required дойти до состояния

, где

—

количество образцов. Переходы из состояния в состояние будут представлять собой добавление одной буквы к тексту, т. е. переход по ребру автомата в другую вершину с соответствующим изменением маски. Запустив обход в ширину на

таком 그래프е, мы найдём путь до состояния

наименьшей длины, что нам как раз и требовалось.

Нахождение лексико그래프ически наименьшей строки длины

, содержащей данные образцы в сумме

раз

Как и в предыдущих 문제х, посчитаем для каждой вершины количество вхождений, которое соответствует ей (т. е. количество помеченных вершин, достижимых из неё по суффиксным ссылкам). Переформулируем задачу

таким образом: текущее состояние определяется тройкой чисел

, и it is required из

состояния

прийти в состояние

, где

— любая vertex. Переходы между состояниями

— это просто переходы по рёбрам автомата из текущей вершины. Таким образом, достаточно просто find обходом в глубину путь между этими двумя состояниями (если обход в глубину будет просматривать буквы в их естественном порядке, то найденный путь автоматически будет лексико그래프ически наименьшим).

Задачи в online judges

Задачи, которые можно решить, используя бор или 알고리즘 Ахо-Корасик:

● UVA #11590 "Prefix Lookup" [Complexity: низкая]

● UVA #11171 "SMS" [Complexity: средняя]

● UVA #10679 "I Love Strings!!!" [Complexity: средняя]

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct vertex {
            int next[K];
            bool leaf;
    };
    vertex t[NMAX+1];
    int sz;
    memset (t[0].next, 255, sizeof t[0].next);
    sz = 1;
    void add_string (const string & s) {
            int v = 0;
            for (size_t i=0; i<s.length(); ++i) {
                    char c = s[i]-'a'; // в зависимости от алфавита
                    if (t[v].next[c] == -1) {
                            memset (t[sz].next, 255, sizeof t[sz].next);
                            t[v].next[c] = sz++;
                    }
                    v = t[v].next[c];
            }
            t[v].leaf = true;
    }
    struct vertex {
            int next[K];
            bool leaf;
            int p;
            char pch;
            int link;
            int go[K];
    };
    vertex t[NMAX+1];
    int sz;
    void init() {
            t[0].p = t[0].link = -1;
            memset (t[0].next, 255, sizeof t[0].next);
            memset (t[0].go, 255, sizeof t[0].go);
            sz = 1;
    }
    void add_string (const string & s) {
            int v = 0;
            for (size_t i=0; i<s.length(); ++i) {
                    char c = s[i]-'a';
                    if (t[v].next[c] == -1) {
                            memset (t[sz].next, 255, sizeof t[sz].next);
                            memset (t[sz].go, 255, sizeof t[sz].go);
                            t[sz].link = -1;
                            t[sz].p = v;
                            t[sz].pch = c;
                            t[v].next[c] = sz++;
                    }
                    v = t[v].next[c];
            }
            t[v].leaf = true;
    }
    int go (int v, char c);
    int get_link (int v) {
            if (t[v].link == -1)
                    if (v == 0 || t[v].p == 0)
                            t[v].link = 0;
                    else
                            t[v].link = go (get_link (t[v].p), t[v].pch);
            return t[v].link;
    }
    int go (int v, char c) {
            if (t[v].go[c] == -1)
                    if (t[v].next[c] != -1)
                            t[v].go[c] = t[v].next[c];
                    else
                            t[v].go[c] = v==0 ? 0 : go (get_link (v), c);
            return t[v].go[c];
    }
}

struct vertex {
        int next[K];
        bool leaf;
};
vertex t[NMAX+1];
int sz;
memset (t[0].next, 255, sizeof t[0].next);
sz = 1;
void add_string (const string & s) {
        int v = 0;
        for (size_t i=0; i<s.length(); ++i) {
                char c = s[i]-'a'; // в зависимости от алфавита
                if (t[v].next[c] == -1) {
                        memset (t[sz].next, 255, sizeof t[sz].next);
                        t[v].next[c] = sz++;
                }
                v = t[v].next[c];
        }
        t[v].leaf = true;
}
struct vertex {
        int next[K];
        bool leaf;
        int p;
        char pch;
        int link;
        int go[K];
};
vertex t[NMAX+1];
int sz;
void init() {
        t[0].p = t[0].link = -1;
        memset (t[0].next, 255, sizeof t[0].next);
        memset (t[0].go, 255, sizeof t[0].go);
        sz = 1;
}
void add_string (const string & s) {
        int v = 0;
        for (size_t i=0; i<s.length(); ++i) {
                char c = s[i]-'a';
                if (t[v].next[c] == -1) {
                        memset (t[sz].next, 255, sizeof t[sz].next);
                        memset (t[sz].go, 255, sizeof t[sz].go);
                        t[sz].link = -1;
                        t[sz].p = v;
                        t[sz].pch = c;
                        t[v].next[c] = sz++;
                }
                v = t[v].next[c];
        }
        t[v].leaf = true;
}
int go (int v, char c);
int get_link (int v) {
        if (t[v].link == -1)
                if (v == 0 || t[v].p == 0)
                        t[v].link = 0;
                else
                        t[v].link = go (get_link (t[v].p), t[v].pch);
        return t[v].link;
}
int go (int v, char c) {
        if (t[v].go[c] == -1)
                if (t[v].next[c] != -1)
                        t[v].go[c] = t[v].next[c];
                else
                        t[v].go[c] = v==0 ? 0 : go (get_link (v), c);
        return t[v].go[c];
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct vertex {
            int next[K];
            boolean leaf;
    };
    vertex t[NMAX+1];
    int sz;
    memset (t[0].next, 255, sizeof t[0].next);
    sz = 1;
    void add_string (const string & s) {
            int v = 0;
            for (size_t i=0; i<s.length(); ++i) {
                    char c = s[i]-'a'; // в зависимости от алфавита
                    if (t[v].next[c] == -1) {
                            memset (t[sz].next, 255, sizeof t[sz].next);
                            t[v].next[c] = sz++;
                    }
                    v = t[v].next[c];
            }
            t[v].leaf = true;
    }
    struct vertex {
            int next[K];
            boolean leaf;
            int p;
            char pch;
            int link;
            int go[K];
    };
    vertex t[NMAX+1];
    int sz;
    void init() {
            t[0].p = t[0].link = -1;
            memset (t[0].next, 255, sizeof t[0].next);
            memset (t[0].go, 255, sizeof t[0].go);
            sz = 1;
    }
    void add_string (const string & s) {
            int v = 0;
            for (size_t i=0; i<s.length(); ++i) {
                    char c = s[i]-'a';
                    if (t[v].next[c] == -1) {
                            memset (t[sz].next, 255, sizeof t[sz].next);
                            memset (t[sz].go, 255, sizeof t[sz].go);
                            t[sz].link = -1;
                            t[sz].p = v;
                            t[sz].pch = c;
                            t[v].next[c] = sz++;
                    }
                    v = t[v].next[c];
            }
            t[v].leaf = true;
    }
    int go (int v, char c);
    int get_link (int v) {
            if (t[v].link == -1)
                    if (v == 0 || t[v].p == 0)
                            t[v].link = 0;
                    else
                            t[v].link = go (get_link (t[v].p), t[v].pch);
            return t[v].link;
    }
    int go (int v, char c) {
            if (t[v].go[c] == -1)
                    if (t[v].next[c] != -1)
                            t[v].go[c] = t[v].next[c];
                    else
                            t[v].go[c] = v==0 ? 0 : go (get_link (v), c);
            return t[v].go[c];
    }
}