首页 > 代码库 > AC自动机
AC自动机
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define L 51 #define LL 100000002 using namespace std; char c[11][L],s[LL]; struct Trie { Trie *ch[26],*fail,*last; int who; Trie() { memset(ch,0,sizeof(ch)); fail=NULL; last=NULL; who=0; } void* operator new(size_t size); }*root,*C,*mempool,*q[L*11]; void* Trie :: operator new(size_t size) { if(C==mempool) { C=new Trie[(1<<15)+10]; mempool=C+(1<<15)+10; } return C++; } int n; inline void insert(char *S,int x) { int len=strlen(S); Trie *now=root; for(int i=0;i<len;i++) { if(now->ch[S[i]-‘a‘]==NULL) now->ch[S[i]-‘a‘]=new Trie; now=now->ch[S[i]-‘a‘]; } now->who=x; } inline void build() { q[0]=root; for(int i=0,j=0;i<=j;i++) for(int l=0;l<26;l++) if(q[i]->ch[l]) { Trie *now=q[i]->fail; while(now&&!now->ch[l])now=now->fail; q[i]->ch[l]->fail=now?now->ch[l]:root; q[++j]=q[i]->ch[l]; q[j]->last=q[j]->fail->who?q[j]->fail:q[j]->fail->last; } } inline void Init() { root=new Trie; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",c[i]); insert(c[i],i); } scanf("%s",s); build(); } int sum[11]; inline void work() { Trie *now=root; for(int i=0;s[i];i++) { int to=s[i]-‘a‘; while(now&&!now->ch[to])now=now->fail; now=now?now->ch[to]:root; for(Trie *Now=now;Now;Now=Now->last) sum[Now->who]++; } } inline void print() { for(int i=1;i<=n;i++) printf("%s %d\n",c[i],sum[i]); } int main() { freopen("ACautomata.in","r",stdin); freopen("ACautomata.out","w",stdout); Init(); work(); print(); return 0; }
AC自动机
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。