首页 > 代码库 > ac自动机系列
ac自动机系列
hdu2222这题说的是在一个1000000的长串中找出n个短串是否在其中出现过 最后输出在长串中出现的个数
#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <queue>#include <string>using namespace std;const int maxn =10000*50+100;const int sign_size = 26;map<string,int>ms;struct Acuth{ int ch[maxn][sign_size]; int val[maxn]; int sz; int f[maxn]; int last[maxn]; bool use[10005]; void clear(){ memset(ch[0],0,sizeof(ch[0])); memset(use,false,sizeof(use)); sz=1; ms.clear(); val[0]=0; } int idx(char c){ return c-‘a‘; } void insert(char *s,int v){ int n = strlen(s), u=0; for(int i=0; i<n; ++i){ int c=idx(s[i]); if(ch[u][c]==0){ memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } ms[string(s)]=v; val[u]=v; } void print(int j){ if(j){ use[val[j]] = true; print(last[j]); } } void find(char *T){ int n = strlen(T); int j=0; for(int i=0; i<n; ++i){ int c = idx(T[i]); while(j&&!ch[j][c]) j=f[j]; j=ch[j][c]; if(val[j]) print(j); else if(last[j]) print(last[j]); } } void getFail(){ queue<int> q; f[0]=0; for(int c = 0; c<sign_size; ++c){ int u = ch[0][c]; if(u){ f[u]=0; q.push(u); last[u]=0; } } while(!q.empty()){ int r= q.front(); q.pop(); for(int c=0; c<sign_size; ++c){ int u=ch[r][c]; if(!u){ ch[r][c] = ch[f[r]][c]; continue; } q.push(u); int v = f[r]; while(v&&!ch[v][c]) v=f[v]; f[u]=ch[v][c]; last[u] = val[f[u]]?f[u] : last[f[u]]; } } }}ac;char P[10005][55],text[1000005];int main(){ int t; scanf("%d",&t); while(t--){ ac.clear(); int n; scanf("%d",&n); for(int i=1; i<=n; ++i){ scanf("%s",P[i]); ac.insert(P[i],i); } scanf("%s",text); ac.getFail(); ac.find(text); int ans=0; for(int i=1; i<=n; ++i) if(ac.use[ms[string(P[i])]]==true) ans++; printf("%d\n",ans); } return 0;}
的
ac自动机系列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。