bzoj 4566: [Haoi2016]找相同字符

/**************************************************************
    Problem: 4566
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:1544 ms
    Memory:51024 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4e5+50;
int ch[N][26],fa[N],len[N],cur[N];
int tot=1,last=1,n,tax[N],a[N],fir[N];
char s[N>>1]; long long ans;
void insert(int c)
{
    int x=last,nx=last=++tot;
    len[nx]=len[x]+1; cur[nx]=1;
    for(;x&&!ch[x][c];x=fa[x]) ch[x][c]=nx;
    if(!x) fa[nx]=1;
    else
    {
        int y=ch[x][c];
        if(len[y]==len[x]+1) fa[nx]=y;
        else
        {
            int ny=++tot; fa[ny]=fa[y];
            len[ny]=len[x]+1; fa[y]=fa[nx]=ny;
            memcpy(ch[ny],ch[y],sizeof(ch[y]));
            for(;x&&ch[x][c]==y;x=fa[x]) ch[x][c]=ny;
        }
    }
}
/*
fir 标记 可以表示为以该点为结尾的最长后缀会出现多少次 
处理endpos集合数
开始匹配 如果能到达节点u 那么他的祖先一定会出现并且未被计算过
但是我们不能直接跳到fa 因为往后还能匹配成功
所以我们在此打一个标记 继续往后匹配 
所以该点对答案的贡献就是 (l-len[fa[u]])*cur[u] 因为fa[u]及其祖先会被我们的标记计算 
最后反拓扑一边 累加标记 此时的贡献就是 sec[u]*cur[u]*(len[u]-len[f]) 
*/
int main()
{
    scanf("%s",s+1); n=strlen(s+1);
    for(int i=1;i<=n;i++) insert(s[i]-'a');
    for(int i=1;i<=tot;i++) tax[len[i]]++;
    for(int i=1;i<=tot;i++) tax[i]+=tax[i-1];
    for(int i=1;i<=tot;i++) a[tax[len[i]]--]=i;
    for(int i=tot;i>=1;i--)
        cur[fa[a[i]]]+=cur[a[i]];
    scanf("%s",s+1); n=strlen(s+1);
    int u=1,l=0;
    for(int i=1;i<=n;i++)
    {
        int c=s[i]-'a';
        while(u&&!ch[u][c]) u=fa[u],l=len[u];
        if(!u) u=1,l=0; else ++l,u=ch[u][c];
        ans+=1LL*(l-len[fa[u]])*cur[u]; fir[fa[u]]++;
    }
    for(int i=tot;i>=1;i--)
    {
        int u=a[i],f=fa[u];
        fir[f]+=+fir[u];
        if(u==1) continue;
        ans+=1LL*fir[u]*cur[u]*(len[u]-len[f]);
    }
    printf("%lld\n",ans);
    return 0;
}