AC自动机

  • c9998118
    了解作者
  • C/C++
    开发工具
  • 727B
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2022-05-25 14:04
    上传日期
AC自动机代码,可以参考实现,有一定参考意义
Ans9.zip
  • Ans9.cpp
    1.5KB
内容介绍
#include<bits/stdc++.h> using namespace std; const int maxm=1e6+8; const int maxn=1e4+8; struct ha { int nexta[3]; int fail; int num; }trie[maxm]; int Q[maxm]; bool book[maxm]; int tot; int ans; int n,m; char s[maxn]; void insert(char *ch) { int len=strlen(ch); int root=0; int i,j,k; for(i=0;i<len;i++) { int k=ch[i]-'0'; if(!trie[root].nexta[k]) { trie[root].nexta[k]=++tot; } root=trie[root].nexta[k]; } trie[root].num++; } void Pre() { int head=1,tail=1; int root=0; int i,j,k,u; for(i=0;i<=1;i++) { if(trie[root].nexta[i]) { Q[tail++]=trie[root].nexta[i]; } else { trie[root].nexta[i]=0; } } while(head<tail) { u=Q[head++]; for(i=0;i<=1;i++) { if(!trie[u].nexta[i]) { trie[u].nexta[i]=trie[trie[u].fail].nexta[i]; continue; } else { Q[tail++]=trie[u].nexta[i]; int fail=trie[u].fail; trie[trie[u].nexta[i]].fail=trie[fail].nexta[i]; } } } } void AC(char *ch) { int len=strlen(ch); int i,j,k; int root=0; for(i=0;i<len;i++) { j=ch[i]-'0'; root=trie[root].nexta[j]; k=root; while(k) { ans+=trie[k].num; k=trie[k].fail; } } } int main() { while(~scanf("%d",&n)) { ans=0; int a,b,c,d; memset(trie,0,sizeof trie); ans=0; for(a=1;a<=n;a++) { scanf("%s",s); insert(s); } Pre(); scanf("%d",&m); while(m--) { ans=0; scanf("%s",&s); AC(s); printf("%d\n",ans); } } return 0; }
评论
    相关推荐