HDU 3695 Computer Virus on Planet Pandora(オートマチック)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3695
題意:いくつかのウイルス列と大きな列sを与え、sがウイルス列またはその逆列を含む場合、私たちはそのウイルス列を含むと言った.問sにはどのくらいのウイルス列が含まれていますか?
标题:ウイルス列をオートマトンに挿入する.sとその逆串で走ります.

const int N=6000005;





struct node

{

    int next[26],fail,flag,t;



    void init()

    {

        clr(next,-1);

        fail=-1;

        flag=t=0;

    }

};



node a[N];

int e,n,m;







void insert(char s[],int t)

{

    int i,k,p=0;

    for(i=0;s[i];i++)

    {

        k=s[i]-'A';

        if(a[p].next[k]==-1)

        {

            a[e].init();

            a[p].next[k]=e++;

        }

        p=a[p].next[k];

    }

    a[p].flag=t;

}



queue<int> Q;



void build()

{

    int i,j,k,p,q;

    FOR0(i,26) if(a[0].next[i]!=-1)

    {

        Q.push(a[0].next[i]);

        a[a[0].next[i]].fail=0;

    }

    while(!Q.empty())

    {

        k=Q.front();

        Q.pop();

        for(i=0;i<26;i++)

        {

            if(a[k].next[i]!=-1)

            {

                p=a[k].next[i];

                q=a[k].fail;

                Q.push(p);

                while(q!=-1&&a[q].next[i]==-1) q=a[q].fail;

                if(q!=-1&&a[q].next[i]!=-1) a[p].fail=a[q].next[i];

                else a[p].fail=0;

            }

        }

    }

}







char s[N],s1[N];





void reverse(char *s,int len)

{

    int L=0,R=len-1;

    while(L<R)

    {

        swap(s[L],s[R]);

        L++;

        R--;

    }

}





void init()

{

    int len=strlen(s),L=0,i,j,k,t;

    FOR0(i,len)

    {

        if(s[i]>='A'&&s[i]<='Z') s1[L++]=s[i];

        else if(s[i]=='[')

        {

            k=0;

            j=i+1;

            while(isdigit(s[j]))

            {

                k=k*10+s[j]-'0';

                j++;

            }

            i=j+1;

            FOR0(t,k) s1[L++]=s[j];

        }

    }

    s1[L]=0;

}





int hash[255];



void  find(char *s)

{

    int i,k,p=0,pre;

    for(i=0;s[i];i++)

	{

		k=s[i]-'A';

		while(p>=0&&a[p].next[k]==-1) p=a[p].fail;

		if(p==-1)

		{

		    p=0;

		    continue;

		}

		pre=p=a[p].next[k];

        while(pre>=0&&a[pre].t==0)

        {

            a[pre].t=1;

            hash[a[pre].flag]=1;

            pre=a[pre].fail;

        }

	}

}



int main()

{

    int C;

    RD(C);

    while(C--)

    {

        scanf("%d",&n);

        a[0].init();e=1;

        int i;

        FOR1(i,n) RD(s),insert(s,i);

        build();

        RD(s);

        init();

        clr(hash,0);

        find(s1);

        reverse(s1,strlen(s1));

        find(s1);

        int ans=0;

        FOR1(i,n) ans+=hash[i];

        PR(ans);

    }

    return 0;

}