HDU 2896 病毒侵袭（AC自动机）

又一个AC自动机的入门题。

写得太搓，一直爆内存，把val的类型从int改成short才过= =

遇到单词结点val就保存该单词的id，因为id最多才100，所以用short没问题。

http://acm.hdu.edu.cn/showproblem.php?pid=2896

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
bool vis[501];
char s[100010];
int n, m, cnt, re;
struct ACauto{
    int ch[100001][96];
    short val[100001];
    int f[100001], last[100001];
    int sz;
    void init(){
        sz=1;
        memset(ch[0],0,sizeof(ch[0]));
    }
    int idx(char ch){
        return ch-32;
    }
    void insert(int id){
        int len=strlen(s);
        int u=0;
        int c;
        for(int i=0; i<len; i++){
            c=idx(s[i]);
            if(!ch[u][c]){
                val[sz]=0;
                memset(ch[sz],0,sizeof(ch[sz]));
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=id;
    }
    void getfail(){
        queue<int> Q;
        f[0]=0;
        for(int c=0; c<96; 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<96; c++){
                int u=ch[r][c];
                if(!u)  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 cal(int x){
        while(x){
            if(val[x] && !vis[val[x]]){
                vis[val[x]]=1;
                re++;
            }
            x=last[x];
        }
    }
    int find(int id){
        int len=strlen(s);
        memset(vis,0,sizeof(vis));
        re=0;
        int j=0;
        for(int i=0; i<len; i++){
            int c=idx(s[i]);
            while(j && !ch[j][c])   j=f[j];
            j=ch[j][c];
            cal(j);
        }
        if(!re)   return 0;
        j=0;
        printf("web %d:", id);
        for(int i=1; i<=n; i++){
            if(vis[i])
                printf(" %d", i);
        }
        puts("");
        return 1;
    }
}ac;
int main(){
    while(~scanf("%d", &n)){
        ac.init();
        for(int i=1; i<=n; i++){
            scanf("%s", s);
            ac.insert(i);
        }
        ac.getfail();
        scanf("%d", &m);
        cnt=0;
        for(int i=1; i<=m; i++){
            scanf("%s", s);
            cnt+=ac.find(i);
        }
        printf("total: %d\n", cnt);
    }
    return 0;
}