bzoj 4566 找相同字符 —— 广义后缀自动机

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4566

建出两个串的广义后缀自动机；

统计每个点在两个串中出现次数的子树和，其实就是在两个串中的 right 集合大小；

然后统计答案乘起来即可。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=8e5+;

int n,m,cnt=,fa[xn],go[xn][],l[xn],tax[xn],q[xn],d1[xn],d2[xn];

char dc[xn];

int work(int p,int w)

{

  int nq=++cnt,q=go[p][w]; l[nq]=l[p]+;

  fa[nq]=fa[q]; fa[q]=nq;

  memcpy(go[nq],go[q],sizeof go[q]);

  for(;p&&go[p][w]==q;p=fa[p])go[p][w]=nq;

  return nq;

}

int ext(int p,int w)

{

  if(go[p][w])

    {

      int q=go[p][w];

      if(l[q]==l[p]+)return q; return work(p,w);

    }

  int np=++cnt; l[np]=l[p]+;

  for(;p&&!go[p][w];p=fa[p])go[p][w]=np;

  if(!p)fa[np]=;

  else

    {

      int q=go[p][w];

      if(l[q]==l[p]+)fa[np]=q;

      else fa[np]=work(p,w);

    }

  return np;

}

void rsort()

{

  for(int i=;i<=cnt;i++)tax[l[i]]++;

  for(int i=;i<=cnt;i++)tax[i]+=tax[i-];

  for(int i=cnt;i;i--)q[tax[l[i]]--]=i;

}

int main()

{

  scanf("%s",dc); n=strlen(dc);

  for(int lst=,i=;i<n;i++)lst=ext(lst,dc[i]-'a'+),d1[lst]++;

  scanf("%s",dc); m=strlen(dc);

  for(int lst=,i=;i<n;i++)lst=ext(lst,dc[i]-'a'+),d2[lst]++;

  rsort();

  for(int i=cnt,x;i;i--)d1[fa[x=q[i]]]+=d1[x],d2[fa[x]]+=d2[x];

  ll ans=;

  for(int i=;i<=cnt;i++)ans+=(ll)(l[i]-l[fa[i]])*d1[i]*d2[i];

  printf("%lld\n",ans);

  return ;

}