HDU 2222(AC自动机模板)

AC自动机这个算法网上有很多资料，这里就不多赘述了。

当从一个字符串中查找另一个字符串，我们有快速的算法KMP。

现在的问题是要从一个字符串中查找很多字符串，或者要从多个字符串里分别查找很多字符串。AC自动机就是解决这个问题的。

HDU2222的题意就是要从一个字符串中查找很多字符串，很裸的模板题。不过测试数据相当的水，有很多人错误的程序都AC掉了。

我们把一个字符串中查找很多字符串中的一个字符串成为文本串，很多字符串称为模式串。

AC自动机的算法步骤就是，先用模式串建立一颗字典树，再BFS出带fail指针的字典树，最后拿文本串在这棵字典树中跑就可以了。

一开始写了一发代码。

#include<bits/stdc++.h>
const int maxnode=26;
using namespace std;
struct node
{
    int sum;
    node *next[maxnode];
    node *fail;
    node()
    {
        memset(next,0,sizeof(next));
        sum=0;
        fail=NULL;
    }
};
node *root=new node();
void Insert(string s)
{
    node *p=root;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(p->next[id]==NULL) p->next[id]=new node();
        p=p->next[id]; 
    }
    p->sum++;
}
void Build()
{
    node *p=root;
    queue<node *>que;
    for(int i=0;i<maxnode;i++) 
    {
        if(p->next[i])
        {
            p->next[i]->fail=root;
            que.push(p->next[i]);
        }
        else p->next[i]=root;
    }
    while(que.size())
    {
        p=que.front();que.pop();
        for(int i=0;i<maxnode;i++)
        {
            if(p->next[i]) 
            {
                p->next[i]->fail=p->fail->next[i];
                que.push(p->next[i]);
            }
            else p->next[i]=p->fail->next[i];
            
        }
    }
}
int Query(string s)
{
    int ans=0;
    queue<pair<node*,int> >status;
    node *p=root;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(p->next[id])
        {
            p=p->next[id];
            node *tmp=p;
            while(tmp->sum)
            {
                ans+=tmp->sum;
                status.push(make_pair(tmp,tmp->sum));
                tmp->sum=0;
                tmp=tmp->fail;
            }
        }
    }
    while(status.size())
    {
        pair<node*,int> tmp=status.front();status.pop();
        tmp.first->sum=tmp.second;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            Insert(s);
        }
        Build();
        cin>>s;
        cout<<Query(s)<<endl;
    }
    return 0;
}

Memory Limit Exceeded到死。

调试了一下午才明白，这是多组数据，而我根没有初始化，这样就会导致，后面的数据是在原来的字典树上构造的，相当于数据都累加起来了。必然导致MLE。所以改了一下每次初始化根就好了。

#include<bits/stdc++.h>
const int maxnode=26;
using namespace std;
struct node
{
    int sum;
    node *next[maxnode];
    node *fail;
    node()
    {
        memset(next,0,sizeof(next));
        sum=0;
        fail=NULL;
    }
};
node *root;
void Insert(string s)
{
    node *p=root;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(p->next[id]==NULL) p->next[id]=new node();
        p=p->next[id]; 
    }
    p->sum++;
}
void Build()
{
    node *p=root;
    queue<node *>que;
    for(int i=0;i<maxnode;i++) 
    {
        if(p->next[i])
        {
            p->next[i]->fail=root;
            que.push(p->next[i]);
        }
        else p->next[i]=root;
    }
    while(que.size())
    {
        p=que.front();que.pop();
        for(int i=0;i<maxnode;i++)
        {
            if(p->next[i]) 
            {
                p->next[i]->fail=p->fail->next[i];
                que.push(p->next[i]);
            }
            else p->next[i]=p->fail->next[i];
            
        }
    }
}
int Query(string s)
{
    int ans=0;
    queue<pair<node*,int> >status;
    node *p=root;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(p->next[id])
        {
            p=p->next[id];
            node *tmp=p;
            while(tmp->sum)
            {
                ans+=tmp->sum;
                status.push(make_pair(tmp,tmp->sum));
                tmp->sum=0;
                tmp=tmp->fail;
            }
        }
    }
    while(status.size())
    {
        pair<node*,int> tmp=status.front();status.pop();
        tmp.first->sum=tmp.second;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
    	root=new node();
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            Insert(s);
        }
        Build();
        cin>>s;
        cout<<Query(s)<<endl;
        //Delete(root);
    }
    return 0;
}

然而这个代码虽然可以AC，但是其实是有问题的。比如对于测试数据：
1
2
abc
b
abc
原本应该输出2，但我的程序输出1。由于HDU2222数据比较弱，所以我的程序AC了。

其实是我递归统计的时候弄错了，没有统计完整。接下来才是正确的AC代码：

#include<bits/stdc++.h>
const int maxnode=26;
using namespace std;
struct node
{
    int sum;
    node *next[maxnode];
    node *fail;
    node()
    {
        memset(next,0,sizeof(next));
        sum=0;
        fail=NULL;
    }
};
node *root;
void Insert(string s)
{
    node *p=root;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(p->next[id]==NULL) p->next[id]=new node();
        p=p->next[id]; 
    }
    p->sum++;
}
void Build()
{
    node *p=root;
    queue<node *>que;
    root->fail=root;
    for(int i=0;i<maxnode;i++) 
    {
        if(p->next[i])
        {
            p->next[i]->fail=root;
            que.push(p->next[i]);
        }
        else p->next[i]=root;
    }
    while(que.size())
    {
        p=que.front();que.pop();
        for(int i=0;i<maxnode;i++)
        {
            if(p->next[i]) 
            {
                p->next[i]->fail=p->fail->next[i];
                que.push(p->next[i]);
            }
            else p->next[i]=p->fail->next[i];
            
        }
    }
}
int Query(string s)
{
    int ans=0;
    queue<pair<node*,int> >status;
    node *p=root;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(p->next[id])
        {
            p=p->next[id];
            node *tmp=p;
            while(tmp->sum||tmp->fail!=root)
            {
            	if(tmp->sum)
                {
                	ans+=tmp->sum;
                	status.push(make_pair(tmp,tmp->sum));
                	tmp->sum=0;
				}
                tmp=tmp->fail;
            }
        }
    }
    while(status.size())
    {
        pair<node*,int> tmp=status.front();status.pop();
        tmp.first->sum=tmp.second;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
    	root=new node();
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            Insert(s);
        }
        Build();
        cin>>s;
        cout<<Query(s)<<endl;
        //Delete(root);
    }
    return 0;
}