http://m.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;
}
|
|
|
CALENDER
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | 22 | 23 | 24 | 25 | 26 | 27 | 28 | | 29 | 30 | 31 | 1 | 2 | 3 | 4 |
|
公告
留言簿(8)
隨筆分類
隨筆檔案
ACM Teammates
The One
搜索
積分與排名
最新評論
閱讀排行榜
評論排行榜
Powered By: 博客園
模板提供：滬江博客
|