CF1817F Entangled Substrings

· · 题解

一个非常简洁的基于 基本子串结构 的做法。

什么是基本子串结构？

固定字符串 a。定义两个字符串 b_1,b_2 “同时出现”当且仅当存在一个字符串 b，满足 b_1,b_2 都是 b 的子串，并且 |endpos(b)|=|endpos(b_1)|=|endpos(b_2)|。

显然，“同时出现”关系是一种等价关系。我们考虑分析其中每一个等价类的形态。

对于一个等价类 S，\exists b\in S,\forall b_1\in S,b_1 是 b 的子串，并且 b_1 只在 b 中出现一次，否则与 b_1\in S 矛盾。

设 b_1=b[l\dots r]。我们将 b_1 写在矩阵的第 l 行第 r 列处。

那么 S 就会形成一个右上阶梯，即由 一条从左上到右下的路径 和 矩阵的右上边界 围成的区域。这便是基本子串结构。

如何显式地求出这个结构？

先建出后缀自动机。对于 DAG 上的一条边 (u,v)，如果 u,v 所对应的 endpos 集合大小相同（此时 u 一定只有一条出边），那么就将这条边标记为关键边。

如果只保留关键边，那么每个点入度和出度都至多为 1，因此我们得到了若干条关键链。对于每一条关键链，依次考虑链上的每个节点，第 i 个节点对应右上阶梯的第 i 列。

通过这种方法就可以显示地表示出这个阶梯的形状，时间复杂度 O(n)。

回到原题。

可以发现一个字符串对 (b_1,b_2) 是好的当且仅当满足以下条件：

因此我们只需要考虑每一个阶梯，枚举 b_2 在 b 中出现位置的左端点并用前缀和统计对应的 b_1 的数量即可。

时间复杂度 O(n)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
#define lll __int128
#define pb push_back
int n,o[N],st[N];ll s[N];lll ans;bool vs[N];
char a[N];struct Point {int len,link,ch[26];};
struct SuffixAutomaton
{
    int nw,cntP,sz[N];bool tg[N];vector<int> e[N];
    Point pt[N];SuffixAutomaton() {nw=cntP=1;}
    void ext(int vl)
    {
        int p=nw,p1,t;pt[nw=++cntP].len=pt[p].len+1;tg[nw]=1;
        while(p && !pt[p].ch[vl]) pt[p].ch[vl]=nw,p=pt[p].link;
        if(!p) {pt[nw].link=1;return;}p1=pt[p].ch[vl];
        if(pt[p1].len==pt[p].len+1) {pt[nw].link=p1;return;}
        pt[t=++cntP]=pt[p1];pt[t].len=pt[p].len+1;pt[nw].link=pt[p1].link=t;
        while(p && pt[p].ch[vl]==p1) pt[p].ch[vl]=t,p=pt[p].link;   
    }
    void dfs(int u) {sz[u]=tg[u];for(auto v:e[u]) dfs(v),sz[u]+=sz[v];}
    void build() {for(int i=2;i<=cntP;++i) e[pt[i].link].pb(i);dfs(1);}

}SAM;
void wr(lll x) {if(x<10) {putchar(x+48);return;}wr(x/10);putchar(x%10+48);}
void slv(int len)
{
    for(int i=1;i<=st[0];++i) s[i]=s[i-1]+st[i];
    for(int i=len-st[0]+1,t=1;i<=len+1 && i<=st[st[0]];++i)
    {while(t<=st[0] && st[t]<i) ++t;ans+=s[i-len+st[0]-1]*(st[0]-t+1);}
}
int main()
{
    scanf("%s",a+1);n=strlen(a+1);
    for(int i=1;i<=n;++i) SAM.ext(a[i]-'a');SAM.build();
    for(int i=1,t;i<=SAM.cntP;++i) for(int j=0;j<26;++j)
    {t=SAM.pt[i].ch[j];if(t && SAM.sz[i]==SAM.sz[t]) o[i]=t,vs[t]=1;}
    for(int i=1,t=0;i<=SAM.cntP;++i) if(!vs[i])
    {
        for(int j=i;j;j=o[j])
            t=j,st[++st[0]]=SAM.pt[j].len-SAM.pt[SAM.pt[j].link].len;
        slv(SAM.pt[t].len);st[0]=0;
    }wr(ans);return 0;
}