AC自动机
题意：输入若干个单词，对于每个单词，计算它在所有单词中出现的次数（原题讲的什么鬼）。
attention：有重复单词，还很多
显然，我们可以用AC自动机来搞
但是对每个单词都需要跑一遍要用极大的空间来存-->MLE。
于是我们想到用一个主串把这些单词拼在一起，中间用特殊符号隔开。这样我们就只要在主串上跑一遍AC自动机就可以了
但是这样还不够（90pts）
于是我们就要对AC自动机进行优化（以后都这样写吧qwq）。
引入一个last指针，保存某节点沿fail指针向前跳最近一个有结尾标记的节点，询问时直接按last指针代替fail指针跳转。搞定
对于重复单词：用一个pre数组存储某编号对应单词的结尾节点
end.
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct data{ int nxt[26],end,fail,last; }a[1000002]; int n,cnt,pre[202]; long long f[202]; string q,g; inline void Trie_build(int id){ cin>>q; g=g+"#"+q; //用string方便地加上各个单词 int u=0,len=q.size(); for(int i=0;i<len;++i){ int p=q[i]-'a'; if(!a[u].nxt[p]) a[u].nxt[p]=++cnt; u=a[u].nxt[p]; } if(!a[u].end) a[u].end=id; pre[id]=a[u].end; //重复单词处理 } inline void AC_build(){ queue <int> h; for(int i=0;i<26;++i) if(a[0].nxt[i]) h.push(a[0].nxt[i]); while(!h.empty()){ int x=h.front(); h.pop(); for(int i=0;i<26;++i){ int &to=a[x].nxt[i]; if(to){ a[to].fail=a[a[x].fail].nxt[i]; a[to].last= a[a[to].fail].end ? a[to].fail:a[a[to].fail].last; //last指针优化 h.push(to); }else to=a[a[x].fail].nxt[i]; } } } inline void AC_query(){ int u=0,len=g.size(); for(int i=0;i<len;++i){ if(g[i]=='#') {u=0; continue;} u=a[u].nxt[g[i]-'a']; for(int j=u;j;j=a[j].last) ++f[a[j].end]; //按last指针跳转 } for(int i=1;i<=n;++i) printf("%lld ",f[pre[i]]); //输出的是 指向的节点 的编号 的值 } int main(){ //freopen("P3966.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;++i) Trie_build(i); AC_build(); AC_query(); return 0; }