题解 洛谷P4094 [HEOI2016/TJOI2016]字符串

发表于 更新于 分类于 本文字数： 5k 阅读时长 ≈ 5 分钟

后缀数组 + 主席树上二分

题意

已知小写字符串 ss 。
mm 次询问，每次询问串 ss 中子串 s[c...d]s[c...d] 与子串 s[a...b]s[a...b] 中每个子串的 lcplcp 长度的最大值。
其中 1≤∣s∣,m≤1051 \leq |s|, m \leq 10^5 。

思路

由于字符串 ss 是给定的，可以 O(nlogn)O(nlogn) 地预处理出 ss 的后缀数组，从而可以 O(1)O(1) 地求出某两个后缀的 lcplcp 长度。
很容易发现答案具有二分性，可以二分出 lcplcp 的长度从而转换为存在性问题。
假设当前二分的结果是 midmid ，可以发现 只有起点位于 [a...b−mid+1][a...b-mid+1] 内的子串与 s[c...d]s[c...d] 的 lcplcp 长度可能大于等于 midmid ，所以问题即转换为求 [a...b−mid+1][a...b-mid+1] 内的后缀与后缀 cc 的 lcplcp 长度。
因为是多组询问，不可能每一次都将 cc 与 [a...b−mid+1][a...b-mid+1] 中的每一个后缀比较一次。考虑后缀数组的性质， rka,rka+1,...rkb−mid+1rk_a, rk_{a+1}, ...rk_{b-mid+1} 与 rkcrk_c 放置在数轴上是一系列散点，由 lcp(rki,rkj)==min(heightk)(rki≤k≤rkj)lcp(rk_i,rk_j) == min(height_k) (rk_i \leq k \leq rk_j) 可以发现只需要计算 rkcrk_c 左右最近的两个位置与它的 lcplcp 即可。具体实现时，可以对串 ss 的下标可持久化建树，每次加入 rkirk_i ，单次询问需要查询 xx 左右的第一个 11 的位置，查询一次复杂度为 O(logn)O(logn) 。所以处理一次询问的复杂度为 O(log2n)O(log^2n) 。
预处理加 nn 次询问的总复杂度为 O(n⋅log2n)O(n \cdot log^2n) 。

代码

代码实现有点极长，不过都是很常规的操作，重点在熟练度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;

constexpr int N=1e5+5;

int n,m;
int a,b,c,d;
struct SA{
    int n,m;
    char s[N];
    int sa[N],rk[N],height[N],h[N];
    int minn[21][N],lg[N];
    void init(int _n,int _m){
        n=_n;
        m=_m;
    }
    void buildsa(){
        static int oldrk[N<<1],id[N],px[N],cnt[N];
        int i,p,w;
        for(i=1;i<=m+1;i++) cnt[i]=0;
        for(i=1;i<=n+1;++i) sa[i]=rk[i]=id[i]=px[i]=0;
        for(i=1;i<=n*2;i++) oldrk[i]=0;
        for(i=1;i<=n;++i) ++cnt[rk[i]=(s[i]-'a'+1)];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
        for(w=1;;w<<=1,m=p){
            for(p=0,i=n;i>n-w;--i) id[++p]=i;
            for(i=1;i<=n;++i)
            if(sa[i]>w) id[++p]=sa[i]-w;
            for(i=1;i<=m;i++) cnt[i]=0;
            for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
            for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
            for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
            for(i=1;i<=n;i++) oldrk[i]=rk[i];
            for(p=0,i=1;i<=n;++i)
            rk[sa[i]]=(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])?p:++p;
            if(p==n){
                for(i=1;i<=n;++i) sa[rk[i]]=i;
                break;
            }
        }
    }
    void buildheight(){
        for(int i=1;i<=n+1;++i) height[i]=h[i]=0;
        int k=0;
        for(int i=1;i<=n;i++){
            if(rk[i]==1) continue;
            if(k) --k;
            int j=sa[rk[i]-1];
            while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
            height[rk[i]]=k;
        }
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++) minn[0][i]=height[i];
        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++) minn[j][i]=min(minn[j-1][i],minn[j-1][i+(1<<(j-1))]);
    }
    int get_lcp(int l,int r){
        if(l==r) return n-l+1;
        l=rk[l],r=rk[r];
        if(l>r) swap(l,r);
        l++;
        int k=lg[r-l+1];
        return min(minn[k][l],minn[k][r-(1<<k)+1]);
    }
}sa;
struct tree{
    int tot;
    int rt[N];
    int lc[N<<5];
    int rc[N<<5];
    int sum[N<<5];
    void cpy(int x,int y){
        lc[x]=lc[y];
        rc[x]=rc[y];
        sum[x]=sum[y];
    }
    void build(int &x,int l,int r){
        if(!x) x=++tot;
        sum[x]=0;
        if(l==r) return;
        int mid=l+r>>1;
        build(lc[x],l,mid);
        build(rc[x],mid+1,r);
        return;
    }
    void update(int &x,int pre,int l,int r,int pos){
        x=++tot;
        cpy(x,pre);
        if(l==r){
            sum[x]++;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid) update(lc[x],lc[pre],l,mid,pos);
        else update(rc[x],rc[pre],mid+1,r,pos);
        sum[x]=sum[lc[x]]+sum[rc[x]];
        return;
    }
    int findr(int r1,int r2,int l,int r,int pos){
        if(l==r) return l;
        int res=-1;
        int mid=l+r>>1;
        if(mid>=pos&&sum[lc[r2]]-sum[lc[r1]]>0) res=findr(lc[r1],lc[r2],l,mid,pos);
        if(res!=-1) return res;
        if(sum[rc[r2]]-sum[rc[r1]]>0) res=findr(rc[r1],rc[r2],mid+1,r,pos);
        return res;
    }
    int findl(int r1,int r2,int l,int r,int pos){
        if(l==r) return l;
        int res=-1;
        int mid=l+r>>1;
        if(mid+1<=pos&&sum[rc[r2]]-sum[rc[r1]]>0) res=findl(rc[r1],rc[r2],mid+1,r,pos);
        if(res!=-1) return res;
        if(sum[lc[r2]]-sum[lc[r1]]>0) res=findl(lc[r1],lc[r2],l,mid,pos);
        return res;
    }
}t;

int check(int mid){
    int l=t.findl(t.rt[a-1],t.rt[b-mid+1],1,n,sa.rk[c]),
        r=t.findr(t.rt[a-1],t.rt[b-mid+1],1,n,sa.rk[c]);
    int res=0;
    if(l!=-1) res=max(res,sa.get_lcp(c,sa.sa[l]));
    if(r!=-1) res=max(res,sa.get_lcp(c,sa.sa[r]));
    return res>=mid;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    cin>>sa.s+1;
    sa.init(n,26);
    sa.buildsa();
    sa.buildheight();
    t.build(t.rt[0],1,n);
    for(int i=1;i<=n;i++) t.update(t.rt[i],t.rt[i-1],1,n,sa.rk[i]);
    while(m--){
        cin>>a>>b>>c>>d;
        int l=0,r=min(b-a+1,d-c+1),ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<'\n';
    }

    return true&&false;
}