AC 自动机 —— WA 自动机? TLE 自动机?

笔记

例题 HDU2222 Keywords Search

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int ncnt, n, ans;
//ncnt: 数一下节点数；bcnt: 数一下模式串(B)的数目； 
char A[1000005], B[1000005];
struct node {
    bool found;
    int id, cnt; 
    node *fail, *nxt[26]; 
    //id: 以该节点结尾的最后一个单词
    //cnt: 以该节点结尾的单词数目
    //fail: 该节点的后缀和fail指针指向的节点后缀相同 
    //nxt: 该节点的一个字符边指向的节点指针 
    node(){
        id = cnt = found = 0;
        ncnt++;
        fail = NULL;
        for(int i = 0; i < 26; i++)
            nxt[i] = NULL;
    }
} *root, *super_root;
//root: trie树的根节点 
//super_root: 为了方便地处理fail指针而创建的“根节点的前缀指针” 
void init(){
    for(int i = 0; i < 26; i++)
        super_root -> nxt[i] = root;
    root -> fail = super_root;
    //super指针的所有字符边指向root 
    //root的fail指针是super_root 
    node *q[ncnt]; 
    int r;
    q[r = 0] = root;
    //用队列，bfs处理fail指针 
    for(int l = 0; l <= r; l++){
        node *u = q[l];//取队首 
        for(int i = 0; i < 26; i++){
            //重点！ 
            node *w = u -> nxt[i], *v = u -> fail;
            //w: 要构建fail指针的节点
            while(v -> nxt[i] == NULL) v = v -> fail;
            //v: 第一个有(u, w)这条边的后缀节点
            //如果一直到根节点都没有，v是super_root 
            v = v -> nxt[i];
            //v变成了w的等效节点(w的fail) 
            if(w != NULL)
                w -> fail = v, q[++r] = w;
            //如果w真实存在(即(u, w)边存在, 则 w的 fail 是 v，将w入队 
            else
                u -> nxt[i] = v;
            //如果w不存在则u的这条字符边直接连向v 
        }
    }
}
void insert(char *s){
    node *now = root;
    int l = strlen(s);
    for(int i = 0; i < l; i++){
        if(now -> nxt[s[i] - 'a'] == NULL)
            now -> nxt[s[i] - 'a'] = new node;
        now = now -> nxt[s[i] - 'a'];
    }
    now -> cnt++;
}
void search(char *s){
    node *now = root;
    int l = strlen(s);
    for(int i = 0; i < l; i++){
        now = now -> nxt[s[i] - 'a'];
        node *tmp = now; //以这个节点结尾的单词不止一个 
        while(tmp != root){//所以这个节点的每个fail指针都要看一下 
            if(!tmp -> found) ans += tmp -> cnt; 
            tmp -> found = 1;
            tmp = tmp -> fail;
        }
    }
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        ans = ncnt = 0;
        root = new node, super_root = new node;
        for(int i = 1; i <= n; i++){
            scanf("%s", B);
            insert(B);
        }
        init();
        scanf("%s", A);
        search(A);
        printf("%d\n", ans);
    }
    return 0;
}