Алгоритм Ахо-Корасик: как построить fail-ссылки для множественного поиска?

Ахо-Корасик — это КМП, обобщённый на множество шаблонов. Сначала строим бор из всех шаблонов. Затем для каждого узла считаем fail-ссылку — указатель на узел, соответствующий наибольшему собственному суффиксу текущего префикса, который тоже является префиксом какого-то шаблона. Это прямой аналог префикс-функции.

fail-ссылки строятся BFS по уровням: fail корня и его детей — корень; для узла u с родителем p по символу c, fail(u) = переход по c из fail(p). Удобно сразу строить «автоматные» переходы go[v][c], чтобы при обходе текста не лазить по fail-цепочке.

struct AhoCorasick {
    struct Node { array<int,26> go; int fail = 0; bool leaf = false; Node(){ go.fill(-1);} };
    vector<Node> t{1};
    void add(const string& s){ int v=0; for(char ch:s){int c=ch-'a'; if(t[v].go[c]==-1){t[v].go[c]=t.size(); t.emplace_back();} v=t[v].go[c];} t[v].leaf=true; }
    void build(){
        queue<int> q;
        for(int c=0;c<26;++c){ if(t[0].go[c]==-1) t[0].go[c]=0; else { t[t[0].go[c]].fail=0; q.push(t[0].go[c]); } }
        while(!q.empty()){
            int v=q.front(); q.pop();
            for(int c=0;c<26;++c){
                int u=t[v].go[c];
                if(u==-1){ t[v].go[c]=t[t[v].fail].go[c]; }   // автоматный переход
                else { t[u].fail=t[t[v].fail].go[c]; q.push(u); }
            }
        }
    }
};

Построение — O(Σ|шаблонов| · алфавит). Дальше текст обрабатывается за O(|text| · алфавит) (с автоматными переходами — без откатов по fail).