非AC版，會T，待更新

#include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include<cmath> #include<ctime> #include<set> #include<map> #include<stack> #include<cstring> #pragma GCC optimize(2) #define inf 2147483647 #define ls rt<<1 #define rs rt<<1|1 #define lson ls,nl,mid,l,r #define rson rs,mid+1,nr,l,r #define N 400010 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(a) putchar(a) #define g() getchar()using namespace std; int n; char s[N],t[2000010]; int d[2000010]; namespace AC{int tr[N][26],tot;int cnt[N],fail[N],id[N],val[N];void insert(char *s,int ID){int u=0;for(int i=1;s[i];i++){if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;u=tr[u][s[i]-'a'];}if(id[u])d[id[u]]=ID;id[u]=ID;}queue<int>q;void build(){For(i,0,25) if(tr[0][i])q.push(tr[0][i]);while(!q.empty()){int u=q.front();q.pop();For(i,0,25)if(tr[u][i]){fail[tr[u][i]]=tr[fail[u]][i];q.push(tr[u][i]);}elsetr[u][i]=tr[fail[u]][i];}}void query(char *t){int u=0;for(int i=1;t[i];i++){u=tr[u][t[i]-'a'];for(int j=u;j;j=fail[j])val[j]++;}For(i,0,tot)if(id[i])cnt[id[i]]=val[i];} } void in(int &x){int y=1;char c=g();x=0;while(c<'0'||c>'9'){if(c=='-')y=-1;c=g();}while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=g();}x*=y; } void o(int x){if(x<0){p('-');x=-x;}if(x>9)o(x/10);p(x%10+'0'); }int find(int x){if(!d[x]) return AC::cnt[x];return AC::cnt[x]=find(d[x]); }int main(){in(n);For(i,1,n){scanf("%s",s+1);AC::insert(s,i);}AC::build();scanf("%s",t+1);AC::query(t);For(i,1,n)o(find(i)),p('\n');return 0; }

?

轉載于:https://www.cnblogs.com/war1111/p/11256651.html

總結

以上是生活随笔為你收集整理的P5357 【模板】AC自动机（二次加强版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。