[HDU][3965][AC自动机] Computer Virus on Planet Pandora

题目大意

---

思路

---

代码

---

#include
#include
using namespace std;

#define T_SIZE 5100000
#define P_SIZE 1000
#define TOTAL_P 250

struct trie
//利用结构体来封装字典树的节点。
{
    trie* next[26];
    trie* fail;
    int num;
    trie()
    //构造函数。
    {
        for(int i=0;inext[s[i]-'A']==NULL)
            p->next[s[i]-'A']=new trie;
        p=p->next[s[i]-'A'];
    }
    p->num++;
}

void  build_ac_automation(trie* root)
//利用广搜构建失败指针 
{
    int head=0,tail=0;
    q[tail++]=root;
    while(head!=tail)
    {
        trie* front=q[head++];
        //front为队头元素 
        for(int i=0;inext[i]!=NULL)
            //遍历队头元素的子节点 
            {
                trie* p=front->fail;
                while(p!=NULL)
                //只有根节点的失败指针为NULL 
                {
                    if(p->next[i]!=NULL)
                    //顺着失败指针往回走，直至某个节点，其拥有一个字母为'A'+i的子节点。 
                    {
                        front->next[i]->fail=p->next[i];
                        break;
                    }
                    p=p->fail;
                }
                if(p==NULL)
                //p==NULL说明顺着失败指针往回走的过程中没有找到合适的节点，所以将失败指针指向根节点。 
                    front->next[i]->fail=root;
                q[tail++]=front->next[i];
            }
    }
}

int ac_find(trie* root,char* T)
{
    trie* p=root;
    int sum=0;
    for(int i=0,len=strlen(T);inext[T[i]-'A']==NULL&&p!=root)
        //若当前节点的没有一个字符为T[i]的儿子且当前节点不是根节点
        //通俗的讲，就是顺着失败指针往回走，直至找到合适的节点或根节点为止。 
            p=p->fail;
        if(p->next[T[i]-'A']!=NULL)
        //p->next[T[i]-'A']==NULL说明没找到合适的节点，p指针指在根节点上。
            p=p->next[T[i]-'A']; 
        trie* temp=p;
        while(temp!=root&&temp->num!=-1)
        //顺着失败指针往回走，一直到根节点。 
        {
            sum+=temp->num;
            //若当前节点的num不为0，则说明以当前节点字母结尾的单词出现过一次。
            //此单词是以上一次循环的节点单词为结尾的单词的子集。 
            temp->num=-1;
            //标记num为-1，避免重复计算。 
            temp=temp->fail;
        }
    }
    return sum;
}

void get_T(char* temp_T)
//解压母串 
{
    int len=strlen(temp_T),len_T=0;
    for(int i=0,num;i='A'&&temp_T[i]='0'&&temp_T[i]<='9')
            num=(num+(temp_T[i]-'0'))*10;
        else if(temp_T[i]==']')
        {
            num/=10;
            for(int k=0;k<num-1;k++)
                T[len_T++]=temp_T[i-1];
        }
    T[len_T]='\0';
}

void reverse(char* str)
//反转字符串 
{
    int len=strlen(str);
    for(int i=0;i0;t--)
    {
        trie* root=new trie;
        int n;
        scanf("%d",&n);
        getchar();
        for(int i=0;i<n;i++)
        {
            gets(P);
            insert(root,P);
        }
        build_ac_automation(root);
        gets(temp_T);
        get_T(temp_T);
        int res=0;
        res=ac_find(root,T);
        reverse(T);
        res+=ac_find(root,T);
        printf("%d\n",res);
    }
}