-
Notifications
You must be signed in to change notification settings - Fork 107
/
Suffix Array.cpp
113 lines (92 loc) · 3.03 KB
/
Suffix Array.cpp
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
// sa[i] -> ith smallest suffix of the string (indexed from 1)
// height[i] -> Longest common substring between Suffix(sa[i]) and Suffix(sa[i-1]), indexed
// from i=2.
// rak[i] -> The position of i th index of the main string in suffix array.
// rak[6]=1 means 6th suffix is in 1st position in sa
const int N = 2e6+5;
int wa[N],wb[N],wv[N],wc[N];
int r[N],sa[N],rak[N], height[N], lg[N];
int cmp(int *r,int a,int b,int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for( i=0;i<m;i++) wc[i]=0;
for( i=0;i<n;i++) wc[x[i]=r[i]] ++;
for( i=1;i<m;i++) wc[i] += wc[i-1];
for( i= n-1;i>=0;i--)sa[--wc[x[i]]] = i;
for( 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++) wc[i] = 0;
for(i=0;i<n;i++) wc[wv[i]] ++;
for(i=1;i<m;i++) wc[i] += wc[i-1];
for(i=n-1;i>=0;i--) sa[--wc[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(int *r,int *sa,int n)
{
int 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 ++) ;
}
}
int dp[N][22];
void initRMQ(int n)
{
for(int i= 1;i<=n;i++) dp[i][0] = height[i];
for(int j= 1; (1<<j) <= n; j ++ ){
for(int i = 1; i + (1<<j) - 1 <= n ; i ++ ) {
dp[i][j] = min(dp[i][j-1] , dp[i + (1<<(j-1))][j-1]);
}
}
}
int askRMQ(int L,int R)
{
int k = lg[R-L+1];
// int k=0;
// while((1<<(k+1)) <= R-L+1) k++;
return min(dp[L][k], dp[R - (1<<k) + 1][k]);
}
// Precalculate powers of two to answer askRMQ in O(1)
int preclg2()
{
for(int i=2; i<N; i++)
{
lg[i]=lg[i-1];
if((i&(i-1))==0) lg[i]++;
}
}
int main()
{
string s; cin>>s;
int n=s.size(), cnt=0;
FOR(i,0,s.size())
{
r[i]=s[i]-'a'+1;
// prnt(r[i]);
cnt=max(cnt,r[i]);
}
r[n]=0; // This is very important, if there are testacases!
da(r,sa,n+1,cnt+1); // cnt+1 is must, cnt=max of r[i]
calheight(r,sa,n);
for(int i=1; i<=n; i++)
printf("sa[%d] = %d\n", i, sa[i]);
for(int i=2; i<=n; i++)
printf("height[%d] = %d\n", i, height[i]);
for(int i=1; i<=n; i++)
printf("rank[%d] = %d\n", sa[i], rak[sa[i]]);
// Must call initRMQ(len)
// To find lcp between any two suffix i and j, call askRMQ(L+1,R)
// where L=min(rak[sa[i]],rak[sa[j]]), R=max(rak[sa[i]],rak[sa[j]]).
/* A Reminder: Sometimes when we concatenate strings, we do that by adding
separators. We might need to add same separator or different separators.
And it might also need to add a separator at the end of the total strings.
*/
return 0;
}