脚本宝典收集整理的这篇文章主要介绍了hdu2222(AC自动机),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Time LimIT: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
total Submission(s): 87731 Accepted Submission(s): 30561
题意:给出n个关键字字符串,然后给出一个字符串s,问有多少个关键字字符串出现在字符串s。
看到这道题,发现这是一道字符串匹配的题,那么很容易想到KMP来解,然而当关键字足够多的时候,那么肯定超时,用trie树也一样,这时我们需要一个新的算法来解决这个问题了:AC自动机。
这里给出一篇关于AC自动机的博客吧:https://bestsort.cn/2019/04/28/402/
@H_406_83@#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; int tre[maxn][30]; int sum[maxn]; char ch1[maxn]; char ch[105]; queue<int> que; int fail[maxn]; void insert(char * ch,int & cnt){ int rt=0; int len=strlen(ch); for(int i=0;i<len;i++){ int tem=ch[i]-‘a‘; if(tre[rt][tem]==0){ tre[rt][tem]=++cnt; } rt=tre[rt][tem]; } sum[rt]++; return ; } void getfail(){ while(!que.empty())que.pop(); int Now=0; for(int i=0;i<26;i++){ if(tre[Now][i]==0)continue; que.push(tre[Now][i]); } while(!que.empty()){ Now=que.front(); que.pop(); // cout<<Now<<endl; for(int i=0;i<26;i++){ if(tre[Now][i]!=0){ fail[tre[Now][i]]=tre[fail[Now]][i]; que.push(tre[Now][i]); } else{ tre[Now][i]=tre[fail[Now]][i]; } } } // puts("YES"); } int query(char * ch){ int len=strlen(ch); int ans=0; int Now=0; for(int i=0;i<len;i++){ Now=tre[Now][ch[i]-‘a‘]; for(int j=Now;j&&sum[j]!=-1;j=fail[j]){ ans+=sum[j]; sum[j]=-1; } } return ans; } int main(){ int t; scanf("%d",&t); while(t--){ int n; int cnt=0; memset(sum,sizeof(sum)); memset(fail,sizeof(fail)); memset(tre,sizeof(tre)); scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s",ch); insert(ch,cnt); } getfail(); scanf("%s",ch1); printf("%d\n",query(ch1)); } return 0; }
以上是脚本宝典为你收集整理的hdu2222(AC自动机)全部内容,希望文章能够帮你解决hdu2222(AC自动机)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。