题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2222
题目大意：多个模式串。问匹配串中含有多少个模式串。注意模式串有重复，所以要累计重复结果。
解题思路：
AC自动机模板题。
一开始使用LRJ的坑爹静态模板，不支持重复的模式串。
在做AC自动机+DP的时候，扒了zcwwzdjn大神的动态优化（失配指向root）写法，以及借鉴了网上的AC自动机模板，
搞出了这么一个支持重复串的模板。
注意在计算last后缀链接的时候，都会修改last->cnt=0，是为了防止同一个模式串在匹配时候走了多遍。比如模：AA，匹：AAA,
修改last->cnt的结果是1，而不修改就是2。修改法在碰到HDU 2896这种需要计算多个匹配串的时候就萎了。
必须在修改之后，及时恢复。由于本身就使用了queue，所以修改时用queue记录一下哪些last被修改了，之后恢复一下就OK！
同时，修改法在HDU 3065中，统计一个模式串出现多少次也萎了。因为模式串必须要走多遍。
#include "cstdio"
#include "cstring"
#include "iostream"
#include "queue"
#include "string"
using namespace std;
struct Trie
{
Trie *next[],*fail;
int cnt;
}*root;
struct status
{
Trie *last;
int cnt;
status(Trie *last,int cnt):last(last),cnt(cnt) {}
};
Trie *newnode()
{
Trie *ret=new Trie;
memset(ret->next,,sizeof(ret->next));
ret->fail=;
ret->cnt=;
return ret;
}
void init() {root=newnode();}
void Insert(string str)
{
Trie *pos=root;
for(int i=;i<str.size();i++)
{
int c=str[i]-'a';
if(!pos->next[c]) pos->next[c]=newnode();
pos=pos->next[c];
}
pos->cnt++;
}
void getfail()
{
queue<Trie *> Q;
for(int c=;c<;c++)
{
if(root->next[c])
{
root->next[c]->fail=root;
Q.push(root->next[c]);
}
else root->next[c]=root;
}
while(!Q.empty())
{
Trie *x=Q.front();Q.pop();
for(int c=;c<;c++)
{
if(x->next[c])
{
x->next[c]->fail=x->fail->next[c];
Q.push(x->next[c]);
}
else x->next[c]=x->fail->next[c];
}
}
}
int find(string str)
{
Trie *pos=root,*last;
queue<status> Q;
int ans=;
for(int i=;i<str.size();i++)
{
int c=str[i]-'a';last;
if(pos->next[c])
{
pos=pos->next[c];
last=pos;
while(last->cnt)
{
Q.push(status(last,last->cnt));
ans+=last->cnt;
last->cnt=; //修改last->cnt
last=last->fail;
}
}
}
while(!Q.empty()) //恢复last->cnt
{
status x=Q.front();Q.pop();
x.last->cnt=x.cnt;
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int T,n;
string tt;
cin>>T;
while(T--)
{
cin>>n;
init();
for(int i=;i<=n;i++)
{
cin>>tt;
Insert(tt);
}
getfail();
cin>>tt;
int ans=find(tt);
printf("%d\n",ans);
}
}
| 11927003 | 2014-10-21 01:22:37 | Accepted | 2222 | 390MS | 29480K | 1942 B | C++ | Physcal |