fzu Problem 2005 Computer Virus on Planet Pa

      #include<iostream>

#include<cmath>

#include<cstdio>

#include<string>

#include<cstring>

#include<vector>

#include<stack>

#include<queue>

#include<set>

#include<map>

#include<algorithm>



#define LL long long



using namespace std;



const int INF=0x3f3f3f3f;

const int N=5500005;

const int M=255000;

const int K=26;

struct nodeTrie

{

    int v;

    int fail;

    int next[K];

    void initialize()

    {

        v=0;

        fail=-1;

        memset(next,-1,sizeof(next));

    }

}trie[M];

int cnt,root;

char s1[N];

char s[1005];

char pro[N];

int getNewNode()

{

    ++cnt;

    trie[cnt].initialize();

    return cnt;

}

void addWord(int p,char *s,int k)

{

    if(s[0]=='\0') return ;

    for(int i=0;s[i]!='\0';++i)

    {

        if(trie[p].next[s[i]-'A']==-1)

        trie[p].next[s[i]-'A']=getNewNode();

        p=trie[p].next[s[i]-'A'];

    }

    (trie[p].v)=k;

}

void init(int n)

{

    cnt=-1;

    root=getNewNode();

    for(int i=1;i<=n;++i)

    {

        gets(s);

        addWord(root,s,i);

    }

}

void bfs(int p)

{

    trie[p].fail=root;

    queue<int>qt;

    qt.push(p);

    while(!qt.empty())

    {

        int y;

        int x=qt.front();qt.pop();

        for(int i=0;i<K;++i)

        if(trie[x].next[i]!=-1)

        {

            qt.push(trie[x].next[i]);

            if(x==root)

            {trie[trie[x].next[i]].fail=root;continue;}

            y=trie[x].fail;

            while(y!=root&&trie[y].next[i]==-1)

            y=trie[y].fail;

            if(trie[y].next[i]!=-1)

            trie[trie[x].next[i]].fail=trie[y].next[i];

            else

            trie[trie[x].next[i]].fail=root;

        }

    }

}

int match(int p,char *s,int n)

{

    int wordCount=0;

    int l=0;

    while(s[l]!='\0')

    {

        while(trie[p].next[s[l]-'A']==-1&&p!=root)

        p=trie[p].fail;

        if(trie[p].next[s[l]-'A']!=-1)

        p=trie[p].next[s[l]-'A'];

        ++l;

        int fp=p;

        while(fp!=root)

        {

            if(trie[fp].v==-1)

            break;

            if(trie[fp].v>0)

            {++wordCount;}

            trie[fp].v=-1;

            fp=trie[fp].fail;

        }

        if(wordCount==n)

        break;

    }

    return wordCount;

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        scanf("%d ",&n);

        init(n);

        bfs(root);

        gets(s1);

        int m=0;

        for(int i=0;s1[i]!='\0';++i)

        if(s1[i]=='[')

        {

            int sum=0;

            for(++i;s1[i]>='0'&&s1[i]<='9';++i)

            sum=sum*10+s1[i]-'0';

            while(sum--)

            pro[m++]=s1[i];

            ++i;

        }else

        {

            pro[m++]=s1[i];

        }

        pro[m]='\0';

        //puts(pro);

        int ans=match(root,pro,n);

        reverse(pro,pro+m);

        ans+=match(root,pro,n-ans);

        printf("%d\n",ans);

    }

    return 0;

}