YbtOJ 535「后缀数组」相似子串

(Updated: )
oi
, , ,

题目链接：YbtOJ #535

小 A 有一个长度为 $n$ 的数字串 $s$，下标为 $1\sim n$。

对于两个 长度相等 的字符串 $A,B$，设它们的长度为 $len$，则定义 $A,B$ 相似 当且仅当对 $\forall 1\le i,j\le len$，$[A_i=A_j]=[B_i=B_j]$（即 $A_i$ 与 $A_j$ 相等充要于 $B_i$ 与 $B_j$ 相等）。

接下来小 A 会进行 $q$ 次询问，每次询问 $s$ 中有多少个子串与 $s[l_i : r_i]$ 相似（包括 $s[l_i : r_i]$ 自身）。这里的 $s[l_i : r_i]$ 意为由 $s$ 中第 $l_i\sim r_i$ 个字符依次拼接得到的字符串。

强制在线。

$1\le n\le 10^5$，$1\le q\le 5\times10^5$。

Solution

对于字符串 $S$，可以将每种字符的上一次出现位置与此位置作差，作为本位置的值。

这样转化后如果两个字符串相似则转化后的数组完全相同。

那么也就可以转化为 $[l1:]$ 与 $[l2:]$ 的 $\text{LCP}$ 长度超过区间长度 $L$ 。

注意到后缀转化后的数组同原串转化后的数组最多只会相差 $10$ 位（每种字符第一次出现的位置有差异）。

于是我们以这 $10$ 个位置为关键点，分段进行比较。

所以我们先对原串转化成的数组建立后缀数组，这样一来若要求解两个后缀转化成的数组的 $\text{LCP}$，就可以直接 按关键点划分成若干段，将每一部分依次比较。

既然能够求出 $\text{LCP}$，那么只要比较 $\text{LCP}$ 的后一位就能比较两个不同后缀转化成的数组的字典序，也就可以将所有后缀转化成的数组做一遍排序。

然后，预先求出排名相邻的后缀的 $\text{LCP}$（类似于一般后缀数组中的 Height 数组）。

询问时在这个 “Height 数组” 上分别向左向右二分一下即可。

发现其实也并不需要使用后缀数组，求 $\text{LCP}$ 直接 Hash+二分 也行，就是复杂度上多了只 $\log$。

Code

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
/*
超！还卡哈希！
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,base=13,base2=17,P=998244353;
int n,q,a[N],rk[N],p[N],F[N][25],H[N][11],lg[N],v[N],pw[N],hsh[N],hsh2[N],pw2[N];
char s[N];vector<int> G[N];
#define pb push_back

struct ST{
    int dp[600010][51];
    void get(int *s,int n){
        for(int i=1;i<=n;i++){
            dp[i][0]=s[i];
        }
        for(int j=1;j<=(log(n)/log(2))+1;j++){
            for(int i=1;i<=n-(1<<j)+1;i++){
                dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int ask(int x,int y){
        int p=(log(y-x+1)/log(2));
        int Min=min(dp[x][p],dp[y-(1<<p)+1][p]);
        return Min;
    }   
}st;
struct SA {
    int rnk[N],sa[N],tme[N],sec[N],height[N],n,sigma;
    void Sort() {
        for(int i=0; i<=sigma; i++)tme[i]=0;
        for(int i=1; i<=n; i++)tme[rnk[i]]++;
        for(int i=1; i<=sigma; i++)tme[i]+=tme[i-1];
        for(int i=n; i>=1; i--)sa[tme[rnk[sec[i]]]--]=sec[i];
        memset(sec,0,sizeof(sec));
    }
    void GetSa(int *s) {
        for(int i=1; i<=n; i++)rnk[i]=s[i],sec[i]=i;
        Sort();
        for(int w=1,p=0; w<=n&&p<n; w<<=1,sigma=p) {
            p=0;
            for(int i=n-w+1; i<=n; i++)sec[++p]=i;
            for(int i=1; i<=n; i++)if(sa[i]>w)sec[++p]=sa[i]-w;
            Sort();
            swap(sec,rnk);
            rnk[sa[1]]=p=1;
            for(int i=2; i<=n; i++) {
                rnk[sa[i]]=(sec[sa[i-1]]==sec[sa[i]]&&sec[sa[i-1]+w]==sec[sa[i]+w])?  p:++p;
            }
        }
    }
    void GetHeight(int *s) {
        int k=0;
        for(int i=1; i<=n; i++) {
            if(k)k--;
            int j=sa[rnk[i]-1];
            while(s[i+k]==s[j+k])k++;
            height[rnk[i]]=k;
        }
    }
    int getLcp(int l,int r){
        if(l>r){
            int t=r;
            r=l;
            l=t;
        }
        int x=min(rnk[l],rnk[r]);
        int y=max(rnk[l],rnk[r]);
        //cout<<x+1<<" "<<y<<endl;
        return st.ask(x+1,y);
    }
    int init(int *s,int len) {
        sigma=N-5;
        n=len;
        GetSa(s);
        GetHeight(s);
        st.get(height,n);
        return n;
    }
}sa;
/*————————————————
版权声明：本文为CSDN博主「YuckXi」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/tomyking2005/article/details/90105343
————————————————*/

I int Q(CI l,CI r){if(l>r) return 2e9;RI k=lg[r-l+1];return min(F[l][k],F[r-(1<<k)+1][k]);}
I int GetL(CI x,CI L){RI l=1,r=x,mid,X=x;W(l<=r) Q((mid=l+r>>1)+1,x)>=L?X=mid,r=mid-1:l=mid+1;return X;}
I int GetR(CI x,CI L){RI l=x,r=n,mid,X=x;W(l<=r) Q(x+1,mid=l+r>>1)>=L?X=mid,l=mid+1:r=mid-1;return X;}
I bool chk(RI x,RI y,CI mid){return (hsh[x]-1LL*hsh[x+mid]*pw[mid]%P+P)%P==(hsh[y]-1LL*hsh[y+mid]*pw[mid]%P+P)%P&&(hsh2[x]-1LL*hsh2[x+mid]*pw2[mid]%P+P)%P==(hsh2[y]-1LL*hsh2[y+mid]*pw2[mid]%P+P)%P;}
I int LCP(CI x,CI y){if(!x!ya[x]^a[y]) return 0;RI l=0,r=n-max(x,y)+1,mid,X=1;W(l<=r) chk(x,y,mid=l+r>>1)?X=mid,l=mid+1:r=mid-1;return X;}
I int Get(CI x,CI y){RI i=0,xi,yi,tx,ty,t,A=0;for(xi=x,yi=y;xi<=n&&yi<=n;++A,i++,xi=tx+1,yi=ty+1) if(tx=i<G[x].size()?G[x][i]:n+1,ty=i<G[y].size()?G[y][i]:n+1,t=sa.getLcp(xi,yi),t<min(tx-xi,ty-yi)) return A+t;else if(A+=min(tx-xi,ty-yi),(ty-yi)^(tx-xi)tx>nty>n) return A;return A;}
I bool cmp(CI x,CI y){RI i,t=Get(x,y),tx=x+t<=n?a[x+t]:-1,ty=y+t<=n?a[y+t]:-1;for(auto i:G[x]) i==x+t&&(tx=0);for(auto i:G[y]) i==y+t&&(ty=0);return tx<ty;}
I int Qry(RI x,CI L){return GetR(p[x],L)-GetL(p[x],L)+1;}
int main(){
    freopen("similar.in","r",stdin),freopen("similar.out","w",stdout);
    RI i,j,x,y,lst=0;for(read(n,q),scanf("%s",s+1),pw[0]=pw2[0]=i=1;i<=n;i++) a[i]=v[s[i]-'0']?i-v[s[i]-'0']:0,v[s[i]-'0']=i,pw[i]=1LL*pw[i-1]*base%P,pw2[i]=1LL*pw2[i-1]*base2%P;
    for(i=n;i;i--) hsh[i]=(1LL*hsh[i+1]*base%P+a[i])%P,hsh2[i]=(1LL*hsh2[i+1]*base2%P+a[i])%P;for(i=n;i;i--){for(j=0;j<=9;j++) H[i][j]=H[i+1][j];H[i][s[i]-'0']=i;for(j=0;j<=9;j++) H[i][j]&&(G[i].pb(H[i][j]),0);sort(G[i].begin(),G[i].end());}

    sa.init(a,n);

    for(i=1;i<=n;i++) rk[i]=i;for(stable_sort(rk+1,rk+n+1,cmp),i=1;i<=n;i++) p[rk[i]]=i;
    for(lg[0]=-1,i=1;i<=n;i++) lg[i]=lg[i>>1]+1,F[i][0]=Get(rk[i-1],rk[i]);for(j=1;(1<<j)<=n;j++) for(i=2;i+(1<<j)-1<=n;i++) F[i][j]=min(F[i][j-1],F[i+(1<<j-1)][j-1]);
    W(q--) read(x,y),x^=lst,y^=lst,writeln(lst=Qry(x,y-x+1));return 0;
}