SAM 表示子串维护包含关系

· · 题解

Part1 前言

认识到自己才疏学浅，开始学习算法并认真记录。

我之前的 SAM 相关文章大多只写到了后缀接受理论和 parent 树 LCA 的相关技巧，但本题需要考虑到 parent 树边的实际含义，也可以通过反串后缀树来进一步理解，相比与之前要复杂很多。

虽然对大多数人看来是板子，但我之前确实不会。

Part2 问题引入

题目链接

给定字符串序列 s_i，字符串集合 T（初始为空），在线进行 q 组询问。

询问 1 向集合 T 加入新的字符串 t_i；

询问 2 给定 p,l,r，设 f(p,l,r) 表示 s_p 的子串区间 [l,r] 在集合 T 的多少个字符串中出现过，求 \max\limits_{i=1}^lf(p,i,r)。

容易发现 \forall i < j\le r,f(p,i,r)\le f(p,j,r)，所以相当于求 f(p,l,r)。

Part3 对模式串的处理

对 s_i 建广义后缀自动机，也可以拼接之后建后缀自动机，我们尝试去表示一个字符串区间。

对于一个字符串区间 s_{x,[l,r]}，我们可以先找到 s_{x,[1,r]} 所对应的自动机节点 y。

设 f_x 表示 x 在 parent 树上的父亲，len_x 表示 x 所对应 endpos 等价类的最长串长度。

我们发现如果有 len_{f_y}\ge r-l+1，就可以让 y 跳到它的父亲，这样我们就能够找到该串所对应的 endpos 等价类。

这时可以尝试使用一个二元组 (x,k) 表示节点 x 等价类中长度为 k 的字符串来表示询问的模式串。

Part4 对文本串的处理

考虑表示出来 t_i 在后缀自动机上能接受的所有子串。

找到 t_i 的每一个前缀在后缀自动机上的位置，注意这里不一定能够保留完整的前缀，而且我们依旧需要记录二元组 (x,k) 来表示这些前缀。

这里可以看作将一条 parent 树上的边 (x,f_x) 分成了 len_x-len_{f_x} 段，每个二元组都能通过边上的点得到表示。

我们可以认为一个节点所对应的字符串是该串的子串当且仅当该节点子树内包含该串某一个前缀所代表的节点。

于是我们变成了对于一些点集到根链的节点并加一，这类问题可以使用一类容斥差分办法，即先全部到根链加，然后 dfn 相邻的节点 LCA 到根链减即可。

到根链加单点查可以直接转换为单点加子树查，即单点加区间查，于是可以做到 O(n\log n)。

Part5 对深搜序的处理

注意到上面将一条边分成若干段导致了点数是 O(n^2) 的，在深搜时用 dfn_x=cnt+len_x-len_{f_x} 可以计算出 dfn，这样只需要使用动态开点的线段树就能做出这道题，因为子树所包含的区间依旧可以轻松求出来。

不过实际实现时为了避免 long long 的计算和减少常数可以在整点上用树状数组维护，虚点的统计只会贡献到自己这条边上，这样对于每一条边都开一棵动态开点线段树即可，这里为了减少细节可以先将存在包含关系的祖先使用单调栈弹掉，这样实点的 LCA 就等于虚点的 LCA 了。

无论使用什么做法，时间复杂度总是 O((\sum|s_i|+\sum|t_i|+q)\log\sum|s_i|+\sum|s_i||\Sigma|) 的，空间 O(\sum|s_i|(\log\sum|s_i|+|\Sigma|))。

Part6 与后缀树的关系

我们发现一条边中间能够裂开许多虚点对一个自动机来说很不自然。

首先从自动机的角度来看就是一个 endpos 等价类有多大这条边就有多长。

但这实质上是反串的后缀树，也就是将反串的所有后缀插到 Trie 上压缩之后的结果。

然后我们发现 SAM 上的跳 parent 的效果是保留后缀，删除前缀，恰好对应反串的后缀树上的删除后缀。

于是这样我们能够更加容易地表示出一个字符串与 SAM 所对应的字符串之间的关系。

给出本题代码以及注释：

#include<icecream>
int T,n,m,K,tp,A,B,C,t[N][26],cnt=1,lst=1,ln[N],f[N],ans;
int dt,dfn[N]实点深搜序,low[N],dlt,de[N],g[N],ct[N],b[N];
vt lk[N],h[100005];parent 树边、模式串前缀所对应节点。
void ins(int p){建立广义 SAM，也可以使用顺序拼接的 SAM。
    int tg=0;
    if(t[lst][p]){
        if(ln[t[lst][p]]==ln[lst]+1){
            lst=t[lst][p];return;
        }else tg=1;
    }int x=++cnt,y,z,r;ln[x]=ln[lst]+1;
    for(y=lst;y&&!t[y][p];y=f[y])t[y][p]=x;
    if(!y)f[x]=1;
    else if(ln[z=t[y][p]]==ln[y]+1)f[x]=z;
    else{
        ln[r=++cnt]=ln[y]+1;
        memcpy(t[r],t[z],sizeof(t[r])),f[r]=f[z];
        while(y&&t[y][p]==z)t[y][p]=r,y=f[y];
        f[x]=f[z]=r;
    }lst=tg?r:x;
}
string s[N];
struct dat{
    int x,k;
    bool operator<(const dat &z)const{
        return x==z.x?k>z.k:dfn[x]>dfn[z.x];
    }
}d[N];
void dfs(int x){
    if(de[g[f[x]]]<<1==de[f[x]]+de[g[g[f[x]]]])g[x]=g[g[f[x]]];
    else g[x]=f[x];
    dfn[x]=++dlt;
    for(int y:lk[x])de[y]=de[x]+1,dfs(y);
    low[x]=dlt;
}
int lca(int x,int y){
    if(de[x]<de[y])swap(x,y);
    while(de[x]>de[y])
        x=de[g[x]]<de[y]?f[x]:g[x];
    while(x!=y){
        if(g[x]==g[y])x=f[x],y=f[y];
        else x=g[x],y=g[y];
    }
    return x;
}
void upd(int x,int k){树状数组维护实点贡献。for(x=dfn[x];x<=cnt;x+=x&-x)ct[x]+=k;}
namespace ZYFDNSGT{（动态开点线段树，区间为 [ln[f[x]]+1,ln[x]])）
    int t[T][2],sm[T],cnt;
#define ls t[x][0]
#define rs t[x][1]
    void cg(int &x,int l,int r,int p){
        if(!x)x=++cnt;++sm[x];
        if(l<r){
            int md=l+r>>1;
            if(p>md)cg(rs,md+1,r,p);
            else cg(ls,l,md,p);
        }
    }
    void ask(int x,int l,int r,int L,int R){
        if(!x)return;
        if(l>=L&&r<=R){ans+=sm[x];return;}
        int md=l+r>>1;
        if(L<=md)ask(ls,l,md,L,R);
        if(md<R)ask(rs,md+1,r,L,R);
    }
}
int in(int x,int y){是否在子树内。return dfn[x]>=dfn[y]&&dfn[x]<=low[y];}
int main(){
    int i,j,k,l,r,x,y,z;
    cin>>n>>T>>tp;
    for(i=1;i<=n;++i){
        cin>>s[i],lst=1;
        for(char c:s[i])ins(c-'a');
    }
    for(x=2;x<=cnt;++x)lk[f[x]].push_back(x);
    for(i=1;i<=n;++i){
        h[i]={x=1};
        for(char c:s[i])
            h[i].push_back(x=t[x][c-'a']);
    }
    de[1]=1,dfs(1);
    while(T--){
        cin>>k;
        if(k==1){
            string s;cin>>s,k=s.size();
            x=1,r=dt=0;
            for(i=0;i<k;++i){
                l=s[i]-'a';找到每个前缀所对应的二元组。
                while(x&&!t[x][l])r=ln[x=f[x]];
                if(!x){x=1;continue;}
                d[++dt]={x=t[x][l],++r};
            }
            if(!dt)continue;
            sort(d+1,d+dt+1);
            for(i=1,r=dt,dt=0;i<=r;++i)弹掉包含的祖先。
                if(!(dt&&in(d[dt].x,d[i].x)))d[++dt]=d[i];
            for(i=1;i<=dt;++i){
                upd(f[x=d[i].x],1);
                ZYFDNSGT::cg(b[x],ln[f[x]]+1,ln[x],d[i].k);
            }
            for(i=1;i<dt;++i){容斥掉相邻的 LCA。
                x=lca(d[i].x,d[i%dt+1].x);
                upd(x,-1);
            }
        }else{
            cin>>x>>l>>r;
            x=h[x][r],r=r-l+1;
            while(ln[f[x]]>=r)倍增跳到所在节点。
                if(ln[f[g[x]]]>r)x=g[x];
                else x=f[x];
            ans=0;
            for(i=low[x];i;i-=i&-i)ans+=ct[i];实点贡献。
            for(i=dfn[x]-1;i;i-=i&-i)ans-=ct[i];
            ZYFDNSGT::ask(b[x],ln[f[x]]+1,ln[x],r,ln[x]);虚边贡献查询。
            printf("%d\n",ans);
        }
    }
    return 0;
}