【题意】

给n个病毒字符串和一个程序字符串，若程序字符串包含某个病毒字符串或者它的反串，则包含这个病毒，问所给程序字符串包含多少个病毒？

【解题方法】

用病毒串和反串建立AC自动机，然后求包含多少病毒，但同一个病毒可能会被计算2次（如果病毒和它的反串都出现在程序中），对于每个病毒，它在自动机中都有2个结点代表自身结尾和反串结尾，我们对每个病毒都记录这2个结点，在统计的过程中可以把走过的结点打上标记，最后再统计哪些病毒的2个结点都被标记，说明被统计了2次，需要减去一次，这样就没问题了。但是题中说了程序串是压缩的，所以需要先需处理

这题我咋死活过不了啊。最后连输入外挂都上了，还是TLE。可能是模板问题？我找了一份AC代码，先放上来，下来研究研究。可能是我的AC自动机太慢？

【别人的AC 代码】原创地址


#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define N 251
#define NODE 500010
#define LEN 5100010
int n,node,x[N],y[N];
int next[NODE][26],fail[NODE],cnt[NODE];
bool vis[NODE];
char S[LEN],tmp[LEN];
int newnode()
{
    memset(next[node],0,sizeof(next[0]));
    fail[node]=cnt[node]=0;
    return node++;
}
void insert(char *s,int id)
{
    int i,k,cur;
    for(i=cur=0; s[i]; i++)
    {
        k=s[i]-'A';
        if(!next[cur][k])   next[cur][k]=newnode();
        cur=next[cur][k];
    }
    cnt[cur]++;
    x[id]=cur;
    for(i--,cur=0; i>=0; i--)
    {
        k=s[i]-'A';
        if(!next[cur][k])   next[cur][k]=newnode();
        cur=next[cur][k];
    }
    cnt[cur]++;
    y[id]=cur;
}
void makenext()
{
    queue<int>q;
    int u,v,k;
    q.push(0);
    while(!q.empty())
    {
        u=q.front(),q.pop();
        for(int k=0; k<26; k++)
        {
            v=next[u][k];
            if(v)   q.push(v);
            else    next[u][k]=next[fail[u]][k];
            if(u&&v)    fail[v]=next[fail[u]][k];
        }
    }
}
void read()
{
    char c;
    int p=0,t=0;
    while(c=getchar(),c!='\n')
    {
        if(t==0&&(c>='A'&&c<='Z'))
        {
            S[p++]=c;
        }
        else if(t!=0&&(c>='A'&&c<='Z'))
        {
            while(t--)S[p++]=c;
        }
        else if(c=='['||c==']')
        {
            t=0;
        }
        else if(c>='0'&&c<='9')
        {
            t=t*10+c-48;
        }
    }
    S[p]='\0';
}
int main()
{
    int T;
    char s[1001];
    scanf("%d",&T);
    while(T--)
    {
        node=0,newnode();
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%s\n",s);
            insert(s,i);
        }
        makenext();
        read();

        int ans=0,i,k,cur;
        memset(vis,0,sizeof(vis));
        for(i=cur=0; S[i]; i++)
        {
            k=S[i]-'A';
            cur=next[cur][k];
            for(int t=cur; t&&cnt[t]!=-1; t=fail[t])
            {
                ans+=cnt[t];
                cnt[t]=-1;
                vis[t]=1;
            }
        }
        for(int i=0; i<n; i++)
        {
            if(vis[x[i]]&&vis[y[i]])    ans--;
        }
        printf("%d\n",ans);
    }
    return 0;
}

【我的死活过不来了代码，下来研究研究】

#include <queue>
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5100100;
const int maxm = 500010;
const int maxs = 26;
char s[1010];
int nn;char s1[maxn],s2[maxn],s3[maxn];
int len2;
void read()
{
    char c;
    int p=0,t=0;
    while(c=getchar(),c!='\n')
    {
        if(t==0&&(c>='A'&&c<='Z'))
        {
            s1[p++]=c;
        }
        else if(t!=0&&(c>='A'&&c<='Z'))
        {
            while(t--)s1[p++]=c;
        }
        else if(c=='['||c==']')
        {
            t=0;
        }
        else if(c>='0'&&c<='9')
        {
            t=t*10+c-48;
        }
    }
    s1[p]='\0';
}
void change(){
    int len1=strlen(s1),num,i,j;
    len2=0;
    for(i=0;i<len1;i++){
        if(s1[i]>='A'&&s1[i]<='Z'){
            s2[len2++]=s1[i];
            continue;
        }
        if(s1[i]=='['){
            i++;
            num=0;
            for(;s1[i]>='0'&&s1[i]<='9';i++){
                num=num*10+s1[i]-'0';
            }
            int ll=len2;
            for(j=ll;j<ll+num;j++){
                s2[j]=s1[i];
                len2++;
            }
            i+=1;
        }
    }
    s2[len2]='\0';
    for(i=0;i<len2;i++){
        s3[i]=s2[len2-i-1];
    }
    s3[len2]='\0';
}
struct Acautomata{
    int root,sz;
    int nxt[maxm][maxs],fail[maxm],cnt[maxm];
    int newnode()
    {
        cnt[sz]=0;
        memset(nxt[sz],-1,sizeof(nxt[0]));
        return sz++;
    }
    void init()
    {
        sz=0;
        root=newnode();
    }
    void Insert(char *s)
    {
        int u=root,n=strlen(s);
        for(int i=0; i<n; i++)
        {
            int &v=nxt[u][s[i]-'A'];
            if(v==-1) v=newnode();
            u=v;
        }
        ++cnt[u];
    }
    void build()
    {
        queue<int>q;
        fail[root]=root;
        for(int i=0; i<maxs; i++){
            int &v=nxt[root][i];
            if(~v){
                fail[v]=root;
                q.push(v);
            }else{
                v=root;
            }
        }
        while(q.size())
        {
            int u=q.front();q.pop();
            for(int i=0; i<maxs; i++)
            {
                int &v=nxt[u][i];
                if(~v){
                    fail[v]=nxt[fail[u]][i];
                    q.push(v);
                }else{
                    v=nxt[fail[u]][i];
                }
            }
        }
    }
    int queryans(char *s)
    {
        int u=root,n=strlen(s);
        int ans=0;
        for(int i=0; i<n; i++)
        {
            u=nxt[u][s[i]-'A'];
            for(int v=u; v!=root; v=fail[v]){
                ans+=cnt[v];
                cnt[v]=0;
            }
        }
        return ans;
    }
}ac1;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&nn);
        ac1.init();
        for(int i=1; i<=nn; i++)
        {
            scanf("%s",s);
            ac1.Insert(s);
        }
        getchar();
        ac1.build();
        read();
        //cout<<s1<<endl;
        change();
        int ans = 0;
        ans += ac1.queryans(s2);
        ans += ac1.queryans(s3);
        printf("%d\n",ans);
    }
    return 0;
}