http://www.shnenglu.com/mythit/archive/2009/07/30/80633.html
http://www.cnblogs.com/destinydesigner/archive/2009/10/15/1584191.html
推薦以上兩個鏈接作為了解AC自動機的材料，加上2006年的一篇Trie圖的論文。
模板+代碼如下：   HDU 2222
#include<iostream>
#include<queue>
using?namespace?std;
struct?Trie
{
????Trie?*next[26];
????Trie?*fail;
????int?cnt;
????Trie()
????{
????????cnt=0;
????????memset(next,NULL,sizeof(next));
????????fail=NULL;
????}
}?*root;
void?build()
{
????root=NULL;
????root=new?Trie;?
}
void?insert(char?*s)
{
????Trie?*r=root,*p;
????int?i=0;
????while(s[i])
????{
????????if(r->next[s[i]-'a']==NULL)
????????{
????????????p=new?Trie();
????????????r->next[s[i]-'a']=p;
????????}
????????r=r->next[s[i]-'a'];
????????i++;
????}
????r->cnt++;
}?
void?BuildTrie()
{
????int?i;
????Trie?*r=root,*p,*tmp;
????root->fail=NULL;
????queue<Trie?*>q;
????q.push(root);
????while(!q.empty())
????{
????????p=q.front();
????????q.pop();
????????for(i=0;i<26;i++)
????????????if(p->next[i]!=NULL)
????????????{
????????????????if(p==root)
????????????????????p->next[i]->fail=root;
????????????????else
????????????????{
????????????????????tmp=p->fail;
????????????????????while(tmp!=root&&tmp->next[i]==NULL)
????????????????????????tmp=tmp->fail;
????????????????????if(tmp->next[i]==NULL)
????????????????????????p->next[i]->fail=root;
????????????????????else?p->next[i]->fail=tmp->next[i];
????????????????}
????????????????q.push(p->next[i]);
????????????}
????}
}
int?check(char?*s)
{
????int?c=0;
????Trie?*r=root,*p,*tmp;
????while(*s)
????{
????????int?idx=*s-'a';
????????while(r->next[idx]==NULL&&r!=root)
????????????r=r->fail;
????????r=r->next[idx];
????????if(r==NULL)
????????????r=root;
????????tmp=r;
????????while(tmp!=root)
????????{
????????????c+=tmp->cnt;
????????????tmp->cnt=0;
????????????tmp=tmp->fail;
????????}
????????s++;
????}
????return?c;
}
int?cas,n;
char?txt[1000010],ss[52];
int?main()
{
????scanf("%d",&cas);
????while(cas--)
????{
????????scanf("%d",&n);
????????build();
????????while(n--)
????????{
????????????scanf("%s",ss);
????????????insert(ss);
????????}
????????scanf("%s",txt);
????????BuildTrie();
????????printf("%d\n",check(txt));
????}
????return?0;
}
|
|
公告
留言簿(8)
隨筆分類
隨筆檔案
ACM Teammates
The One
搜索
積分與排名
最新評論
閱讀排行榜
評論排行榜
Powered By: 博客園
模板提供：滬江博客
|