题目链接：http://acm.hdu.edu.cn/showPRoblem.php?pid=2222 思路： 题目大意是，提供n个单词以及一段话，问在这段话中所给单词在文章中出现的个数。使用AC自动机算法来解题。
AC代码：
#include<cstdio>#include<cstring>#include<queue>using namespace std;const int maxn=1000000;char str[maxn+10];struct node{ int count;//标识是否为叶子结点 struct node *next[26]; struct node *fail;//失败指针 void init()//初始化函数 { for(int i=0;i<26;i++) next[i]=NULL; count=0; fail=NULL; } }*root;//构造树TRIEvoid insert(){ node *p=root; int len=strlen(str); for(int i=0;i<len;i++) { int pos=str[i]-'a'; if(p->next[pos]==NULL) { p->next[pos]=new node; p->next[pos]->init(); p=p->next[pos]; } else p=p->next[pos]; } p->count++;//标识为单词尾部 } //构造失败指针 void getfail() { node *p=root,*son,*temp; queue<struct node *>que; que.push(p);//root入队 while(!que.empty()) { temp=que.front(); que.pop(); for(int i=0;i<26;i++) { son=temp->next[i]; if(son!=NULL) { if(temp==root) son->fail=root; else { p=temp->fail; while(p) { if(p->next[i])//如果trie中有相同字母指向该字母的失败指针 { son->fail=p->next[i]; break; } p=p->fail; } if(!p) son->fail=root; } que.push(son); } } } } //查找有多少个字符串在所给段落中出现 void query() { int ans=0; int len=strlen(str); node *p=root,*temp; for(int i=0;i<len;i++) { int pos=str[i]-'a'; while(!p->next[pos]&&p!=root) p=p->fail; p=p->next[pos]; if(!p) p=root; temp=p; while(temp!=root) { if(temp->count>=0)//找到改串单词尾部 { ans+=temp->count; temp->count=-1;//标识该单词找过，避免重复计算 } else break; temp=temp->fail; } } printf("%d/n",ans);//输出个数 } int main() { int m,n; scanf("%d",&m); while(m--) { root=new node; root->init(); root->fail=NULL; scanf("%d",&n); getchar(); for(int i=0;i<n;i++) { scanf("%s",&str); insert();//构造TRIE } getfail();//建立失败指针 scanf("%s",&str); query(); } return 0; }新闻热点
疑难解答
