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];
    }
}