AC自动机

AC自动机，不得不说，很难理解。

这里的代码是《算法竞赛入门经典——训练指南》上的代码，自己把散碎的代码整理了整理。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int maxnode = 1000 + 10;
const int SIGMA_SIZE = 26;

struct AhoCorasicAutomata{
    int f[maxnode], ch[maxnode][SIGMA_SIZE], last[maxnode];
    int val[maxnode];
    int sz;

    int idx(int c) { return c - 'a'; }
    void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); }

    void insert(char *s, int v){
        int u = 0, n = strlen(s);
        for(int i=0; i<n; i++){
            int c = idx(s[i]);
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = v;
    }

    void getFail(){
        queue<int> q;
        f[0] = 0;
        for(int c=0; c<SIGMA_SIZE; c++){
            int u = ch[0][c];
            if(u) { f[u] = 0; q.push(u); last[u] = 0; }
        }

        while(!q.empty()){
            int r = q.front(); q.pop();
            for(int c=0; c<SIGMA_SIZE; c++){
                int u = ch[r][c];
                if(!u) { ch[r][c] = ch[f[r]][c]; continue; }
                q.push(u);
                int v = f[r];
                while(v &&!ch[v][c]) v = f[v];
                f[u] = ch[v][c];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }

    void find(char *T){
        int n = strlen(T);
        int j=0;
        for(int i=0; i<n; i++){
            int c = idx(T[i]);
            j = ch[j][c];

            if(val[j]) print(i, j);
            else if(last[j]) print(i, last[j]);
        }
    }

    void print(int i, int j){
        if(j){
            printf("%d: %d\n", i, val[j]);
            print(i, last[j]);
        }
    }
};

AhoCorasicAutomata ac;
char text[10000], P[151][80];

int main(){
    int n;
    scanf("%d", &n);
    ac.init();
    for(int i=1; i<=n; i++){
        scanf("%s", P[i]);
        ac.insert(P[i], i);
    }
    ac.getFail();
    scanf("%s", text);
    ac.find(text);

    return 0;
}

样例：

3
abc
a
ed
abcedfe

输出解释：

例如对于4:3这个输出，4代表匹配的模版位置为文本串中下标为4的字符(即第5个)，而这个模版是第三个输入的（即ed)。