【后缀数组】洛谷 P2408 不同子串个数
2021-09-23 14:02:00 # ACM

题链

题目解析

求出后缀数组后，得到排序过后的后缀序列，例如：
  $ababca$ 得出的后缀序列为：
  $a$
  $ababca$
  $abca$
  $babca$
  $bca$
  $ca$

对应的三个数组如下：

pos 1 2 3 4 5 6
height 0 1 2 0 1 0
sa 6 1 3 2 4 5
rak 2 4 3 5 6 1

要得到不同字串的个数，每一个字串来源于一个后缀的前缀，由于后缀是按字典序排序过后的，重复的子串只需要考虑相邻两串的重复度，于是可以查看相邻两串重复了多少来去重，可以发现相邻两串重复的恰好就是 $height$ 数组的值，那么对于一个后缀的贡献就是这个后缀的长度 $n-sa_i+1$ 减去 $height_i$，于是 $ans = \sum_{i=1}^{i=n}n-sa_i+1-height_i$；

代码实现

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ULL unsigned long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define B1 131
	#define B2 13331
	#define M1 1000000007
	#define M2 1000000009
	#define eps 1e-8
	#define MAXN 9e18
	#define MS 1000009	

LL n,m,k;
char s[MS];

LL wa[MS],wb[MS],wv[MS],wss[MS],rak[MS],height[MS],cal[MS],sa[MS];

int cmp(LL *r,LL a,LL b,LL l){
	return r[a] == r[b] && r[a+l] == r[b+l];
}

void da(LL *r,LL *sa,LL n,LL M){
	LL i,j,p,*x=wa,*y=wb,*t;
	for(LL i=0;i<M;i++) wss[i] = 0;
	for(LL i=0;i<n;i++) wss[x[i]=r[i]]++;
	for(LL i=1;i<M;i++) wss[i] += wss[i-1];
	for(LL i=n-1;i>=0;i--) sa[--wss[x[i]]] = i;
	for(LL j=1,p=1;p<n;j*=2,M=p){
		for(p=0,i=n-j;i<n;i++) y[p++] = i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++] = sa[i]-j;
		for(i=0;i<n;i++) wv[i] = x[y[i]]; 
		for(i=0;i<M;i++) wss[i] = 0;
		for(i=0;i<n;i++) wss[wv[i]]++;
		for(i=1;i<M;i++) wss[i] += wss[i-1];
		for(i=n-1;i>=0;i--) sa[--wss[wv[i]]] = y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
		x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++; 
	} 
}

void calheight(LL *r,LL *sa,LL n){
	LL i,j,k=0;
	for(i=1;i<=n;i++) rak[sa[i]] = i;
	for(i=0;i<n;height[rak[i++]]=k)
	for(k?k--:0,j=sa[rak[i]-1];r[i+k]==r[j+k];k++);
	for(int i=n;i;i--) rak[i] = rak[i-1],sa[i]++;
}

void solve(){
	cin >> n;
	cin >> s+1;
	for(int i=1;i<=n;i++) cal[i] = s[i];
	cal[n+1] = 0;
	da(cal+1,sa,n+1,200);
	calheight(cal+1,sa,n);
//	LL ans = n*(n+1)/2;
	LL ans = 0;
	for(int i=1;i<=n;i++){
//		ans -= height[rak[i]];
		ans += n-sa[i]+1-height[i];
	}
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
	//cin >> ce;
	while(ce--){
		solve();
	}
}
Prev
2021-09-23 14:02:00 # ACM
Next