UVA1449 Dominating Patterns（AC自动机）

题目链接。

分析：

表示对AC自动机还不能完全理解，所以在纸上手绘了下 getFail 和 find 的过程，表示理解的深刻些了。好，继续加油！

分析详见《算法竞赛入门经典——训练指南》P216。

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

using namespace std;

const int SIGMA_SIZE = 26;
const int maxnode = 150*70 + 10;

struct AhoCorasicAutomata{
    int f[maxnode], ch[maxnode][SIGMA_SIZE], last[maxnode];
    int val[maxnode];
    int cnt[151];
    map<string, int> ms;
    int sz;

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

    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;
        ms[string(s)] = 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]) count(j);
            else if(last[j]) count(last[j]);
        }
    }

    void count(int j){
        if(j){
            cnt[val[j]]++;
            count(last[j]);
        }
    }
};

AhoCorasicAutomata ac;
char text[1000000+10], P[151][80];

int main(){
    int n;
    while(scanf("%d", &n) == 1 && 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);

        int best = -1;

        for(int i=1; i<=n; i++)
            if(ac.cnt[i] > best) best = ac.cnt[i];

        printf("%d\n", best);

        for(int i=1; i<=n; i++)
            if(ac.cnt[ac.ms[P[i]]] == best) printf("%s\n", P[i]);
    }

    return 0;
}