传送门

调了两天终于调出来啦$qwqwqwqwqwq$

把两个串拼一块染个色造$SA​$。

对于它们的子串$S_A,S_B$，设它们分别属于后缀$suffix_i,suffix_j$，则只要$LCP(suffix_i,suffix_j)\ge len(S_A)$两个子串就是相同的。

又有$LCP(suffix_i,suffix_j)=\min\{height[k]\}(i<k\le j)$

那么对于任意一个区间$[l,r]$它会产生$\min\{height[k]\}(k\in (l,r])​$的贡献。

然后就可以用单调栈了。显然选取的两个区间端点颜色要不同，做个前缀和就好了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 400005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int sa[maxn],rk[maxn],hei[maxn],tp[maxn],tax[maxn],ll[maxn],rr[maxn],col[maxn],sum[maxn][2],n,m;
char a[maxn],s[maxn];
struct MonoStack{
    int sta[maxn],top;
    inline void push1(int x){
        while(top>1&&hei[sta[top]]>=hei[x])--top;
        sta[++top]=x;
    }
    inline void push2(int x){
        while(top>1&&hei[sta[top]]>hei[x])--top;
        sta[++top]=x;
    }
    inline void clear(){
        top=0;
    }
    inline int back(){
        return sta[top-1];
    }
}st;//单调栈
void Rsort(){
    for(register int i=0;i<=m;++i)tax[i]=0;
    for(register int i=1;i<=n;++i)++tax[rk[i]];
    for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
    for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
}
void Ssort(){
    for(register int i=1;i<=n;++i)rk[i]=s[i],tp[i]=i;
    m=225,Rsort();
    for(register int k=1,p=0;p<n;m=p,k<<=1){
        p=0;
        for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
        for(register int i=1;i<=n;++i)if(sa[i]>k)tp[++p]=sa[i]-k;
        Rsort();
        for(register int i=1;i<=n;++i)tp[i]=rk[i];
        rk[sa[1]]=p=1;
        for(register int i=2;i<=n;++i)
            rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]?p:++p;
    }
}
void get_height(){
    int k=0,x;
    for(register int i=1;i<=n;++i){
        if(rk[i]==1)continue;
        if(k)--k;
        x=sa[rk[i]-1];
        while(i+k<=n&&x+k<=n&&s[i+k]==s[x+k])++k;
        hei[rk[i]]=k;
    }
}
void solve(){
    long long ans=0;
    st.push1(1);
    for(register int i=1;i<=n;++i)st.push1(i),ll[i]=st.back();
    st.clear(),st.push2(n+1);
    for(register int i=n;i;--i)st.push2(i),rr[i]=st.back()-1;
    for(register int i=1;i<=n;++i)
        sum[i][0]=sum[i-1][0]+(col[sa[i]]==1),sum[i][1]=sum[i-1][1]+(col[sa[i]]==2);//前缀和
    for(register int i=1;i<=n;++i){
        ans+=1ll*hei[i]*((sum[rr[i]][0]-sum[i-1][0])*(sum[i-1][1]-sum[ll[i]-1][1])+(sum[rr[i]][1]-sum[i-1][1])*(sum[i-1][0]-sum[ll[i]-1][0]));
    }

    printf("%lld\n",ans);
}
int main(){
    scanf("%s",s+1),m=strlen(s+1)+1;
    for(register int i=1;i<m;++i)col[i]=1;
    s[m]='$';
    scanf("%s",a+1),n=strlen(a+1);
    for(register int i=1;i<=n;++i)
        s[i+m]=a[i],col[i+m]=2;
    n+=m;
    Ssort(),get_height(),solve();
}