ac自动机（求每个单词在单词所组成的论文中出现的次数）

思路：其实就是求每个单词的前缀中有多少后缀出现过某个单词，如果正向通过单词来枚举每个后缀，复杂度过高，那么我们反着枚举，然后惊奇的发现，这不就是next数组吗！那么就是把原题转化成了一个dag图，只需要把某个后继点的值累加到每个前缀就可以了，最后在插入的时候记录下每个单词的的位置，由于是dag图，我们将bfs的序列反着遍历，把f数组的当前值累加到前驱即可，这样就等价于把他的值给了所有前驱节点。最后查询f[位置]即可。

#include<bits/stdc++.h>
using namespace std;
const int M=1000010;
char str[M];
int ne[M],tr[M][26],idx,cnt[M];
int f[M];
int id[210];
int q[M];
void insert(int x)
{
   
    int p=0;
    for(int i=0;str[i];i++)
    {
   
        int ii=str[i]-'a';
        if(!tr[p][ii])   tr[p][ii]=++idx;
        p=tr[p][ii];
        f[p]++;
    }
    id[x]=p;
}
void build()
{
   
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)
    if(tr[0][i])
    q[++tt]=tr[0][i];
    while(hh<=tt)
    {
   
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
   
            int &p=tr[t][i];
            if(!p) p=tr[ne[t]][i];
            else
            {
   
                ne[p]=tr[ne[t]][i];
                q[++tt]=p;
            }
        }
    }
}
int main()
{
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
   
        scanf("%s",str);
        insert(i);
    }
   // exit(0);
    build();
    //return 0;
    for(int i=idx-1;i>=0;i--)
    {
   
        f[ne[q[i]]]+=f[q[i]];
    }
    for(int i=0;i<n;i++)
    cout<<f[id[i]]<<endl;
    return 0;
}