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

题目：戳这里

题意：求m个网站出现过的病毒串并按id从小到大输出。最后一行输出含有病毒的网站数量。

思路：AC自动机模板题，注意可见字符的范围是128...这题空间卡的比较严。。

代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int maxw = 130;
const int maxn = 210;
const int time = 505;
const int maxs = 10010;

struct DFAAC{
int tire[maxn*time][maxw];
int fail[maxn*time];
int tag[maxn*time];
bool vis[time];
int P , root , tail , stat;
int New(){
        tail = stat = 0;
for(int i=0;i<maxw;i++) tire[P][i] = -1;tag[P] = 0;
return P++;
    }
void init(){
        P=0;root =New();
    }
void Insert(char ch[] , int id){
int now = root;
for(int i=0;ch[i];i++){
if(tire[now][ch[i]]==-1) tire[now][ch[i]] = New();
            now = tire[now][ch[i]];
        }
        tag[now] = id;
    }
void built()
    {
        queue<int>Q;
        fail[root] = root;
for(int i = 0 ; i < maxw;i++){
if(tire[root][i]!=-1){
                Q.push(tire[root][i]);
                fail[tire[root][i]] = root;
            }
else tire[root][i] = root;
        }
while(!Q.empty()){
int u = Q.front();Q.pop();
for(int i=0;i < maxw;i++){
if(tire[u][i]!=-1){
                    fail[tire[u][i]] = tire[fail[u]][i];
                    Q.push(tire[u][i]);
                }
else tire[u][i] = tire[fail[u]][i];
            }
        }
    }
void Match(char ch[]){
        memset(vis,0,sizeof(vis));

int now = root;
for(int i=0;ch[i];i++){
            now = tire[now][ch[i]];
int tmp = now;
while(tmp!=root){
if(tag[tmp]) vis[tag[tmp]] = 1;
                tmp = fail[tmp];
            }
        }
    }

};
DFAAC ac;
char ch[maxs];
int n , m;
vector<int>ans[maxs];
int main()
{
while(~scanf("%d",&n)){
        ac.init();
for(int i=1;i<=n;i++){
            scanf("%s",ch);
            ac.Insert(ch , i);
        }
        ac.built();
        scanf("%d",&m);
for(int i=1;i<=m;i++) ans[i].clear();
for(int i=1;i<=m;i++){
            memset(ac.vis,0,sizeof(ac.vis));
            scanf("%s",ch);
            ac.Match(ch);
for(int j=1;j<=n;j++){
if(ac.vis[j]){
                    ans[i].push_back(j);
                }
            }
        }
int tot = 0;
for(int i=1;i<=m;i++){
int sz = ans[i].size();
if(sz!=0)printf("web %d:",i),tot++;
for(int j = 0 ; j < sz;j++){
                printf(" %d",ans[i][j]);
            }
if(sz!=0)
            printf("\n");
        }
        printf("total: %d\n",tot);
    }
}