P4482 [BJWC2018] Border 的四种求法

Mobius127 · 2023-10-17 22:19:38 · 题解

基本子串结构做法。

题传

推荐阅读

对正反串分别建立 SAM（以下简称正反 SAM）。

我们尝试为每个本质不同子串一种标记方式，对反 SAM 的 parent 树重链剖分（若有子树相同 size 优先选择最后一次出现位置更晚的那个），对于反串 SAM 上的每个结点 a，a 所代表的 startpos 等价类的串，我们以二维坐标表示它们：第一维是 a 所在重链链底的 startpos（SAM 的性质保证了叶子的 startpos 大小为 1），第二维是自己的串长。

通过这样的编号方式，结合基本子串结构相关知识，可以导出以下结论：

1. 对于反串 SAM 的一个结点，其代表的所有等价类在 xOy 平面上为一条竖线段。

2. 对于正串 SAM 的一个结点，其代表的所有等价类在 xOy 平面上为一条斜线段。

3. 对于反串 SAM 的任意一条由上至下的链，其代表的所有等价类在 xOy 平面上仍为一条竖线段。

考虑同时对正 SAM parent 树做树链剖分，区间 border 即为 s[l, r] 在正反 SAM 上的结点到链的一个信息交。同时从正反 SAM 的 parent 树向上跳重链，显然两边的 O(\log n) 条重链只会有 O(\log n) 对有交集。现在问题转化成求正反 SAM parent 树的中的两条重链（的前缀）的交集信息。

将询问挂在正串 SAM 的重链上，离线后枚举每条重链，问题相当于加入 O(n) 条斜线段，O(q\log n) 次查询一条竖线段和其它斜线段的交点的纵坐标最大值。

重新设置坐标，横坐标不变，纵坐标减去原来的横坐标，那么加入的斜线段变成横线段，询问仍然是竖线段。对新的横坐标扫描线，线段树查询区间最靠右不为 1 点即可。复杂度 O((n+q\log n)\log n)。

Code:

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#include <assert.h>
#define mcy(arra, arrb) memcpy(arra, arrb, sizeof(arra))
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){return x+(x<0?cp:0)-(x>=cp?cp:0);}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
    int ret=1;
    for(; b; b>>=1, a=1ll*a*a%cp)
        if(b&1) ret=1ll*ret*a%cp;
    return ret;
}
const int N=2e5+5;
const int M=N<<1;
struct SAM{
    int tr[M][26], len[M], fa[M][21], ndc, lst;
    inline int clr(int x){len[x]=fa[x][0]=0;mcy(tr[x], tr[0]);return x;}
    inline int rmk(){return lst=clr(ndc=1);}
    inline int insert(char cc){
        int p=lst, cur=clr(++ndc), c=cc-'a';len[cur]=len[p]+1;
        for(; p&&!tr[p][c]; p=fa[p][0]) tr[p][c]=cur;int q=tr[p][c];
        if(!q) fa[cur][0]=1;else if(len[p]+1==len[q]) fa[cur][0]=q;
        else{
            int nex=clr(++ndc);len[nex]=len[p]+1, fa[nex][0]=fa[q][0], mcy(tr[nex], tr[q]);
            for(; p&&tr[p][c]==q; p=fa[p][0]) tr[p][c]=nex;fa[q][0]=fa[cur][0]=nex;
        }
        return lst=cur;
    }
    vi G[M];int mxp[M], pos[N], siz[M], son[M], top[M], edr[M];
    void dfs(int x){
        for(int i=1; i<=20; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];int y;siz[x]=1;
        for(auto v:G[x]) dfs(v), siz[x]+=siz[v], mxp[x]=max(mxp[x], mxp[v]),
        y=son[x], son[x]=(siz[y]==siz[v])?(mxp[y]<mxp[v]?v:y):(siz[y]<siz[v]?v:y);
    }
    int id[M], cnt, bac[M], L, R;
    void dfs(int x, int rt){
        top[x]=rt;if(son[x]) dfs(son[x], rt);edr[x]=son[x]?edr[son[x]]:mxp[x];
        for(auto v:G[x]) if(!top[v]) bac[id[v]=++cnt]=v, dfs(v, v), 
        L=min(L, len[x]+1-edr[v]), R=max(R, len[v]-edr[v]);
    }
    void build(char *str, int len){
        L=INF;rmk();for(int i=1; i<=len; ++i) mxp[pos[i]=insert(str[i])]=i;
        for(int i=2; i<=ndc; ++i) G[fa[i][0]].pb(i);dfs(1), son[1]=0;dfs(1, 1);
    }
    inline int mnl(int x){return len[fa[x][0]]+1;}
    inline int find(int x, int y){
        int u=pos[y], k=y-x+1;for(int i=20; i>=0; --i) 
        if(len[fa[u][i]]>=k) u=fa[u][i];return u;
    }
}A, B;
namespace SegmentTree{
    int L, R, mx[M<<2];
    void init(int l, int r){L=l, R=r;}
    #define ls k<<1
    #define rs k<<1|1
    #define mid (l+r>>1)
    void modify(int k, int l, int r, int x, int v){
        if(l==r) return (void)(mx[k]+=v);
        if(x<=mid) modify(ls, l, mid, x, v);
        else modify(rs, mid+1, r, x, v);
        mx[k]=max(mx[ls], mx[rs]);
    }
    void update(int p, int v){modify(1, 1, R-L+1, p-L+1, v);}
    int query(int k, int l, int r, int x, int y){
        if(!mx[k]||x>r||y<l) return -INF;if(l==r) return mid+L-1;
        int t=query(rs, mid+1, r, x, y);return (t!=-INF)?t:query(ls, l, mid, x, y);
    }
    int qry(int l, int r){return query(1, 1, R-L+1, l-L+1, r-L+1);}
    #undef ls
    #undef rs
    #undef mid
}
char s[N];int n, m, ans[N];
struct node{int qid, rid, riq, len;};vector <node> Q[M];
inline void wrk(int id, int l, int r){
    int u=A.find(l, r), v=B.find(n-r+1, n-l+1);
    for(u=A.fa[u][0], v=B.fa[v][0]; u!=1&&v!=1; ){
        int fu=A.top[u], a=A.mnl(fu), b=A.len[u];
        int fv=B.top[v], c=B.mnl(fv), d=B.len[v];
        Q[A.id[fu]].pb((node){id, fv, v, min(r-l, A.len[u])});
        if(a<c) v=B.fa[fv][0];else u=A.fa[fu][0];
        //[a, b] [c, d] [a, c b d]
    }
}
struct seg{int d, x, y, op, qid;};
inline void slv(int lid){
    vector <seg> vec;
    for(int x=A.bac[lid]; x; x=A.son[x]){
        // printf("-->%d ", x);
        int mnl=A.mnl(x), r=A.mxp[x], l=r-mnl+1, u=B.find(n-r+1, n-l+1);
        int linknxt=B.edr[u], k=mnl-linknxt;//[x=linknxt, y=len[x]-k]
        assert(linknxt<=A.len[x]-k);
        vec.pb((seg){linknxt-1, k, k, -2});vec.pb((seg){A.len[x]-k, k, k, 0});
    }
    for(auto v:Q[lid]){
        int x=B.edr[v.rid], l=B.mnl(v.rid), r=min(B.len[v.riq], v.len);
        if(l<=r) vec.pb((seg){x, l-x, r-x, v.qid});\
    }
    sort(vec.begin(), vec.end(), [&](seg a, seg b){if(a.d==b.d) return a.op<b.op;return a.d>b.d;});
    for(auto v:vec){
        if(v.op<=0) SegmentTree :: update(v.x, v.op+1);
        else ans[v.op]=max(ans[v.op], v.d+SegmentTree :: qry(v.x, v.y));
    }
}
signed main(){
    scanf("%s", s+1);n=strlen(s+1);
    A.build(s, n);reverse(s+1, s+n+1);B.build(s, n);m=read();
    for(int i=1, l, r; i<=m; ++i) l=read(), r=read(), wrk(i, l, r);
    SegmentTree :: init(-n-4, n+4);for(int i=1; i<=A.cnt; ++i) slv(i);
    for(int i=1; i<=m; ++i) printf("%d\n", ans[i]);
    return 0;
}

一些实现细节：

我实际上写的重剖是拿在原串中最早出现的重儿子，是本质相同的。

当询问的是重链前缀时，需要对长度进行额外限制。