Hdu2222Keywords Search

xiaoxiao2021-02-27  368

Hdu2222

存一发AC自动机模板…

【代码】

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <queue> #define N 500005 #define INF 1LL<<60 using namespace std; typedef long long ll; ll read() { ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int T,n,cnt; int g[N][26],Next[N],tag[N]; bool Flag[N]; void Clear(int x) { Next[x]=tag[x]=0; memset(g[x],0,sizeof(g[x])); } void Add(char *s) { int len=strlen(s); int now=0; for(int i=0;i<len;i++) { if(!g[now][s[i]-'a']) { Clear(++cnt); g[now][s[i]-'a']=cnt; } now=g[now][s[i]-'a']; } tag[now]++; } void Input_Init() { n=read();cnt=0; Clear(0); for(int i=1;i<=n;i++) { char s[55]; scanf("%s",s); Add(s); } } void Construct() { queue<int>q; for(int i=0;i<26;i++) { int v=g[0][i]; if(v) q.push(v); } while(!q.empty()) { int k=q.front();q.pop(); for(int i=0;i<26;i++) { int &v=g[k][i]; if(v) { q.push(v); Next[v]=k==0?0:g[Next[k]][i]; } else v=k==0?0:g[Next[k]][i]; } } } void Solve() { char ch[1000005];int ans=0; scanf("%s",ch); int len=strlen(ch); for(int i=0,j=0;i<len;i++) { int v=g[j][ch[i]-'a']; while(!v&&j) { j=Next[j]; v=g[j][ch[i]-'a']; } j=v; while(v&&tag[v]!=-1) { ans+=tag[v]; tag[v]=-1; v=Next[v]; } } printf("%d\n",ans); } int main() { T=read(); while(T--) { Input_Init(); Construct(); Solve(); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2511.html

最新回复(0)