题解 洛谷P4770 [NOI2018]你的名字

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

后缀数组 + 主席树上二分，需要双指针优化

题意

给定小写字符串 ss ， qq 次询问，每次给出小写字符串 tt 与整数 l,rl, r ，求 tt 中本质不同的子串个数，满足该子串不出现在 s[l,r]s[l, r] 中。
其中 1≤∣s∣≤5⋅105,1≤q≤105,∑∣t∣≤1061 \leq |s| \leq 5 \cdot 10^5, 1 \leq q \leq 10^5, \sum|t| \leq 10^6 。

思路

对于单次询问，显然可以容斥一下转换成求 tt 与 s[l,r]s[l, r] 的本质不同的公共子串个数，最后再用 tt 的本质不同的子串个数减去它。
对于后者，求出 tt 的后缀数组的同时也就求好了。对于前者，可以考虑对于 tt 的每一个后缀都求出它与 s[l,r]s[l, r] 中子串匹配到的最长距离，最后再用类似后者的方法求出结果。
那么问题转换成了如何求 tt 的每一个后缀与 s[l,r]s[l, r] 中子串匹配到的最长距离。不难想到类似洛谷P4094 [HEOI2016/TJOI2016]字符串中的方法，将 ss 与 tt 拼接在一起，二分出长度再判断，求解复杂度为 O(log2n)O(log^2n) ，总复杂度为 O(∑(∣t∣⋅log2∣t∣))O(\sum(|t| \cdot log^2|t|)) ，由于 ∑∣t∣≤106\sum|t| \leq 10^6 ，显然不行，考虑继续优化。
可以发现该问题与 P4094 不同的地方在于——该题求的串是 tt 中的每一个后缀，也就是连续的若干个后缀，若我们考虑按 tt 中原本的顺序求解，若对于 tt 的第 ii 个后缀，它算出的匹配长度为 lenlen ，那么对于下一个后缀 i+1i + 1 ，它能够匹配到的长度至少为 max⁡(len−1,0)\max(len - 1, 0) 。因此，我们考虑按顺序求出 tt 中每一个后缀的匹配长度，计算时维护当前的长度 lenlen ，从后缀 i−1i - 1 到 ii 时，逐次判断 lenlen 能否继续增长，单次判断的过程类似 P4094 ，复杂度为 O(logn)O(logn) ，由于维护 lenlen 的过程实际上是维护一个双指针，所以求出 tt 中每一个后缀匹配长度的总复杂度为 O(∣t∣⋅log∣t∣)O(|t| \cdot log|t|) ，那么对于所有询问，总复杂度即为 O(∑(∣t∣⋅log∣t∣))O(\sum(|t| \cdot log|t|)) 。
对于所有询问，将询问离线下来，把所有的串 tt 与 ss 拼接后求出后缀数组即可。

代码

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

constexpr int N=2e6+5;

vector<int> pos[N];
int q;
int l[N],r[N];
int fi[N],lst[N];
string s,str[N];
struct SA{
    int n,m;
    char s[N];
    int sa[N],rk[N],height[N],h[N];
    int minn[22][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]-'`'+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=1;i<=n;i++) h[i]=height[rk[i]];
        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){
        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 findl(int rt1,int rt2,int l,int r,int pos){
        if(l==r){
            if(sum[rt2]-sum[rt1]) return l;
            else return -1;
        }
        int mid=l+r>>1;
        int res=-1;
        if(mid+1<=pos&&sum[rc[rt2]]-sum[rc[rt1]]) res=findl(rc[rt1],rc[rt2],mid+1,r,pos);
        if(res!=-1) return res;
        if(sum[lc[rt2]]-sum[lc[rt1]]) res=findl(lc[rt1],lc[rt2],l,mid,pos);
        return res;
    }
    int findr(int rt1,int rt2,int l,int r,int pos){
        if(l==r){
            if(sum[rt2]-sum[rt1]) return l;
            else return -1;
        }
        int mid=l+r>>1;
        int res=-1;
        if(mid>=pos&&sum[lc[rt2]]-sum[lc[rt1]]) res=findr(lc[rt1],lc[rt2],l,mid,pos);
        if(res!=-1) return res;
        if(sum[rc[rt2]]-sum[rc[rt1]]) res=findr(rc[rt1],rc[rt2],mid+1,r,pos);
        return res;
    }
}t;

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>s;
    cin>>q;
    for(int i=1;i<=q;i++) cin>>str[i]>>l[i]>>r[i];
    for(auto c:s) sa.s[++sa.n]=c;
    sa.s[++sa.n]='`';
    for(int i=1;i<=q;i++){
        fi[i]=sa.n+1;
        for(auto c:str[i]) sa.s[++sa.n]=c;
        lst[i]=sa.n;
        sa.s[++sa.n]='`';
        for(int j=fi[i];j<=lst[i];j++) pos[i].push_back(j);
    }
    sa.m=27;
    sa.buildsa();
    sa.buildheight();
    for(int i=1;i<=q;i++)
        sort(pos[i].begin(),pos[i].end(),[&](const int &x,const int &y){
            return sa.rk[x]<sa.rk[y];
        });
    t.build(t.rt[0],1,sa.n);
    for(int i=1;i<=s.size();i++) t.update(t.rt[i],t.rt[i-1],1,sa.n,sa.rk[i]);
    for(int i=1;i<=q;i++){
        ll ans=0;
        int pre=0;
        for(auto x:pos[i]){
            if(pre==0) ans+=lst[i]-x+1;
            else ans+=lst[i]-x+1-min({lst[i]-x+1,lst[i]-pre+1,sa.get_lcp(pre,x)});
            pre=x;
        }
        vector<int> len(lst[i]-fi[i]+1,0);
        int res=0;
        for(int x=fi[i];x<=lst[i];x++){
            res=max(res-1,0);
            while(x+res<=lst[i]&&res+1<=r[i]-l[i]+1&&check(x,l[i],r[i],res+1)) res++;
            len[x-fi[i]]=res;
        }
        pre=0;
        for(int j=0;j<len.size();j++){
            if(j==0) ans-=len[pos[i][j]-fi[i]];
            else ans-=len[pos[i][j]-fi[i]]-min({len[pos[i][j-1]-fi[i]],len[pos[i][j]-fi[i]],sa.get_lcp(pos[i][j-1],pos[i][j])});
        }
        cout<<ans<<"\n";
    }

    return true&&false;
}