【hdu2896】病毒侵襲

我的内心幾乎是崩潰！！

AC自動機模闆題

一開始給每個葉子開了26個兒子，後來RE了，發現沒有規定必須是小寫字母，然後改成130，突然覺得這道題卡記憶體啊，寫完之後果真MLE了，看了别人的部落格發現跟我開同樣大的數組大小沒有事，猛然想到去掉memset這樣的話隻會有100000個結點，是以不會MLE。

此時大概已經這道題已經寫了40分鐘左右了，然後我就開始崩潰了，自測各種資料不出錯，交上去不停WA，于是搜到了zyf2000的部落格，照着她的程式改，= =本來我AC自動機的模闆就是找着她打的而且碼風和她很像（大括号換行嘿嘿，zyz是不換行的異端），直到改到和她變量名不同，其他完全相同的時候，還是在WA，我想難道有不規範的關鍵字，然後又交了一遍，忽然想到是不是輸出的單詞的問題，整個人都懵逼了，趕快檢查自己的程式，web沒有問題啊，total！！！！我簡直想抽自己一巴掌，于是這道題寫了整整兩個小時，整個人都不好了，藍瘦，日了假狗（捂臉）。

貼上改到和zyf2000基本完全相同的代碼。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;
const int N=;
int ch[N][],n,m,sz,fl[N],ed[N],cnt,ans[N];
bool vis[N];
char s[N];
queue<int>q;

void insert(int id)
{
    int len=strlen(s),now=;
    for (int i=;i<len;++i)
    {
        int x=s[i];
        if (!ch[now][x])ch[now][x]=++sz;
        now=ch[now][x];
    }
    ed[now]=id;
}
void make_fail()
{
    while(!q.empty()) q.pop();
    for (int i=;i<=;++i)
    if (ch[][i])q.push(ch[][i]);
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for (int i=;i<=;++i)
        {
            if (!ch[now][i])
            {
                ch[now][i]=ch[fl[now]][i];
                continue;
            }
            fl[ch[now][i]]=ch[fl[now]][i];
            q.push(ch[now][i]);
        }
    }
}
void ac()
{
    int len=strlen(s),now=;
    for (int i=;i<len;++i)
    {
        vis[now]=;
        int x=s[i]; 
        int y=ch[now][x];
        while (y&&!vis[y])
        {
            vis[y]=;
            if (ed[y])ans[++ans[]]=ed[y];
            y=fl[y];
        }
        now=ch[now][x];
    }
}
int main()
{
    scanf("%d\n",&n);
    for (int i=;i<=n;++i)
    {
        gets(s);
        insert(i);
    }
    scanf("%d\n",&m);
    make_fail();
    for (int j=;j<=m;++j)
    {
        gets(s);
        ans[]=;
        memset(vis,,sizeof(vis));
        ac();   
        if (ans[])
        {
            printf("web %d: ",j);
            sort(ans+,ans+ans[]+);
            for (int i=;i<=ans[];++i)
            printf("%d%c",ans[i]," \n"[i==ans[]]);
            ++cnt;
        }
    }
    printf("total: %d\n",cnt);
}