P3181 [HAOI2016]找相同字符[后缀自动机]

2018-05-18

题目描述

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

输入输出格式

输入格式：

两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母

输出格式：

输出一个整数表示答案

输入输出样例

输入样例#1：

1
2

aabb
bbaa

输出样例#1：

题解

广义后缀自动机，然后在parent树上跑一下就好。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
    return k*base;
}
inline void write(int x)
{
    static char cnt,num[15];cnt=0;
    if (!x)
    {
        putchar('0');
        return;
    }
    for (;x;x/=10) num[++cnt]=x%10;
    for (;cnt;putchar(num[cnt--]+48));
}
const int maxn=8e5+10;
const int mxn=2e5+10;
int ch[maxn][27],fa[maxn],dist[maxn],sz[maxn][2];
int np,p,la,n,cnt,rt,m;
char s[mxn],c[mxn];
void insert(int x,int bj)
{
    int v;
    if (bj==0) v=s[x]-'a'; else v=c[x]-'a';
    
    p=la;np=++cnt;dist[np]=x;la=np;sz[np][bj]=1;
    for (;p&&ch[p][v]==0;p=fa[p]) ch[p][v]=np;
    if (p)
    {
        int q=ch[p][v];
        if (dist[q]==dist[p]+1) fa[np]=q;
        else
        {
            int now=++cnt;
            dist[now]=dist[p]+1;
            for (int i=0;i<26;i++) ch[now][i]=ch[q][i];
            fa[now]=fa[q];
            fa[q]=fa[np]=now;
            for (;ch[p][v]==q;p=fa[p]) ch[p][v]=now;
        }
    } else fa[np]=rt;
}
ll ans;
int to[maxn],ne[maxn],po[maxn],id;
#define add(x,y) to[++id]=y,ne[id]=po[x],po[x]=id;
void dfs(int x)
{
    for (int i=po[x];i;i=ne[i])
    {
        dfs(to[i]);
        sz[x][0]+=sz[to[i]][0];
        sz[x][1]+=sz[to[i]][1];
    }
    ans+=(ll)(-dist[fa[x]]+dist[x])*(ll)(sz[x][0])*(sz[x][1]);
}
void work()
{
    for (int i=2;i<=cnt;i++) add(fa[i],i)
    dfs(1);
    printf("%lld\n",ans);
}
int T;
int main()
{
    ans=0;
    scanf("%s",s+1);n=strlen(s+1);
    la=rt=++cnt;
    for (int i=1;i<=n;i++) insert(i,0);
    scanf("%s",c+1);m=strlen(c+1);
    la=rt;
    for (int i=1;i<=m;i++) insert(i,1);
    work();
    return 0;
}