博客

题意比较坑爹。。他的意思是每一个串都是文本。。比如样例，a就不用说了，aa在本身出现一次，aaa中出现两次。

怎么做呢，如果直接暴力匹配是会炸的。但是我们发现如果每个串本身就是文本的话我们是已经遍历过一次的，可以在上面记录一些信息，来达到题目的要求。我们设每个串结束的位置为pos[i]，那么每次插入新串的时候经过的每个地方都把标记+1，然后跑fail的时候吧fail树上的节点全部加起来就是答案了。

表示fail有很多种打法，我现在老是容易混淆，，其实主要都是预处理的区别。。真的醉了。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e6+5;
int n,a[N][30];
int b[N],cnt[N],tot,fail[N],q[N];
char s[N];
inline void ins(int &y)
{
    int x=0,len=strlen(s);
    fo(i,0,len-1)
    {
        int c=s[i]-'a';
        if(!a[x][c])a[x][c]=++tot;
        x=a[x][c];
//printf("%d ",x);
        cnt[x]++;
//printf("%d\n",cnt[x]);
    }
    y=x;
}
inline void getfail()
{
    int t=0,w=0;
    fo(i,0,25)if (a[0][i])q[w++]=a[0][i];
    while (t<w)
    {
        int x=q[t++];
        fo(i,0,25)
        if (a[x][i])
        {
            int j=fail[x],k=a[x][i];
            while (j&&!a[j][i])j=fail[j];
            j=a[j][i];
            fail[k]=j;
            q[w++]=k;
        }
        else a[x][i]=a[fail[x]][i];
    }
    fd(i,w-1,0)
    cnt[fail[q[i]]]+=cnt[q[i]];
}
int main()
{
    scanf("%d",&n);
    fo(i,1,n)
    {
        scanf("%s",s);
        ins(b[i]);
    }
    getfail();
    fo(i,1,n)printf("%d\n",cnt[b[i]]);
}