给你一堆字符串，和一个文本串，求有多少个字符串在文本串出现过
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; const int maxn=550000; struct AC_auto { int chd[maxn][26],v[maxn],f[maxn],last[maxn],sz,ans; void init() { sz=1;ans=0; memset(v,0,sizeof(v)); memset(f,0,sizeof(f)); memset(chd[0],0,sizeof(chd[0])); } void insert(char* p) { int cur=0; for(;*p;p++) { if(!chd[cur][*p-'a']) { memset(chd[sz],0,sizeof(chd[sz])); chd[cur][*p-'a']=sz++; } cur=chd[cur][*p-'a']; } v[cur]++; } bool query(char* p) { int cur=0; for(;*p;p++) { if(!chd[cur][*p-'a']) break; cur=chd[cur][*p-'a']; } return v[cur]&&(!(*p)); } int getFail() { queue<int> q; f[0]=0; for(int c=0;c<26;c++) { int u=chd[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<26;c++) { int u=chd[r][c]; if(!u){ chd[r][c]=chd[f[r]][c];continue;}///.... q.push(u); int vv=f[r]; while(vv&&!chd[vv][c]) vv=f[vv]; f[u]=chd[vv][c]; last[u]=v[f[u]] ? f[u] : last[f[u]]; } } } void solve(int j) { if(!j) return; if(v[j]) { ans+=v[j]; v[j]=0; } solve(last[j]); } void find(char* T) { int n=strlen(T),j=0; getFail(); for(int i=0;i<n;i++) { j=chd[j][T[i]-'a']; if(v[j]) solve(j); else if(last[j]) solve(last[j]); } } }ac; int main(){ int T,n; char s[1000005]; cin>>T; while(T--) { scanf("%d",&n); ac.init(); while(n--) { scanf("%s",s); ac.insert(s); } scanf("%s",s); ac.find(s); printf("%d\n",ac.ans); } return 0; } hdu2222
