HDU 3065 病毒侵袭持续中 AC自动机

2019-11-08 01:20:34

字体：大中小

来源：转载

供稿：网友

#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#define MAXN 50005#define MAXLEN 55using namespace std;int n,m,ans[1005];char a[1005][MAXLEN],b[2000005];struct trie{ int cnt,root; int nx[MAXN][128],fail[MAXN],end[MAXN]; int newnode() { cnt++; fail[cnt]=end[cnt]=0; for(int i=0;i<128;i++) nx[cnt][i]=0; return cnt; } void init() { cnt=0; root=newnode(); memset(ans,0,sizeof(ans)); } void insert(char *s,int id) { int now=root,len=strlen(s); for(int i=0;i<len;i++) { if(!nx[now][s[i]]) nx[now][s[i]]=newnode(); now=nx[now][s[i]]; } end[now]=id; } void build_fail() { queue<int> q; fail[root]=root; int now=root; for(int i=0;i<128;i++) { if(!nx[root][i]) nx[root][i]=root; else fail[nx[root][i]]=root,q.push(nx[root][i]); } while(!q.empty()) { int now=q.front(); for(int i=0;i<128;i++) { if(nx[now][i]) { fail[nx[now][i]]=nx[fail[now]][i]; q.push(nx[now][i]); } else nx[now][i]=nx[fail[now]][i]; } q.pop(); } } void match(char *s) { int sum=0,now=root,len=strlen(s); for(int i=0;i<len;i++) { now=nx[now][s[i]]; int t=now; while(t!=root) { ans[end[t]]++; t=fail[t]; } } for(int i=1;i<=n;i++) if(ans[i]) PRintf("%s: %d/n",a[i],ans[i]); return; }}AC;int main(){ while(scanf("%d",&n)!=EOF) { AC.init(); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { scanf("%s",a[i]); AC.insert(a[i],i); } AC.build_fail(); scanf("%s",b); AC.match(b); } return 0;}

上一篇：树莓派设置默认声卡

下一篇：HDU 2896 病毒侵袭 AC自动机