# Suffix Array template

Sep 3rd, 2020
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3.
4. string s;
5. int n;
6.
8.     const int MaxN = 4e5 + 5e2;
9.     static char Buff[MaxN];
10.     scanf("\n%s" ,Buff);
11.     return Buff;
12. }
13.
14. inline string SubStr(string &Str ,int Start ,int Len = 1e9){
15.     /// --- Give String + StartIdx (If You Want To The End Of String) --- ///
16.     /// --- Give String + StartIdx + Len (If You Want Len Of SubStr) ---- ///
17.
18.     string Res;
19.
20.     int N = (int)Str.size();
21.     Len   = max(0 ,Len);
22.     Start = max(0 ,Start);
23.
24.     for(int i = Start ; (i < N && i < Start + Len) ; i++)
25.         Res += Str[i];
26.     return Res;
27. }
28.
29. void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n){
30.     int N = max(300 ,n);
31.     vector< int > Cnt(N ,0);
32.     vector< int > tempSA(n);
33.
34.     /// --- Count The Repetitions --- ///
35.     for(int i = 0 ; i < n ; i++)
36.         Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;
37.
38.     /// --- Find The Correct Index Of Each Repetition --- ///
39.     for(int i = 0, sum = 0 ; i < N ; i++){
40.         int t = Cnt[i];
41.         Cnt[i] = sum;
42.         sum += t;
43.     }
44.
45.     /// --- Put Each Repetition In It's Right Place --- ///
46.     for(int i = 0 ; i < n ; i++)
47.         tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
48.
49.     /// --- UPD Suffix Array --- ///
50.     SA = tempSA;
51. }
52.
53. void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n){
54.     CountSort(SA ,RA ,s ,n); /// --- Sort By Second --- ///
55.     CountSort(SA ,RA ,f ,n); /// --- Sort By First  --- ///
56.
57.     /// --- Sort The Pair ii(F ,S) --- ///
58. }
59.
60. vector< int > ConstructSA(string &s ,int n){
61.     vector< int > tempRA(n ,0);
62.     vector< int > SA(n ,0) ,RA(n ,0);
63.
64.     for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
65.     for(int i = 0 ; i < n ; i++) SA[i] = i;
66.
67.     for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 ){
68.         /// --- Sort pairs (RA[i] ,RA[i + k]) --- ///
69.         RadixSort(SA ,RA ,k ,0 ,n);
70.
71.         /// --- Give New Ranks After Sorting --- ///
72.         int r = tempRA[ SA[0] ] = 0;
73.         for(int i = 1 ; i < n ; i++){
74.             bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
75.             bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
76.                           RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
77.             tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
78.         }
79.
80.         /// --- UPD Rank Array --- ///
81.         RA = tempRA;
82.     }
83.
84.     return SA;
85. }
86.
87. /// --- Find Str t in Str s --- ///
88. bool Search(vector< int > &Suff ,string &s ,int n ,string &t ,int m){
89.     bool Res = false;
90.
91.     /// --- Binary Search The Suffixes --- ///
92.     int L = 0 ,R = n - 1;
93.     while( L <= R && !Res ){
94.         int Mid = (L + R) >> 1;
95.
96.         string SubSuffString = SubStr(s ,Suff[Mid] ,m);
97.
98.              if( SubSuffString < t ) L = Mid + 1;
99.         else if( SubSuffString > t ) R = Mid - 1;
100.         else Res = true;
101.     }
102.
103.     return Res;
104. }
105.
106. /// --- Count Occurs Of Str t in Str s --- ///
107. int CntOfOccInStr(vector< int > &Suff ,string &s ,int n ,string &t ,int m){
108.
109.     /// --- Binary Search The Suffixes Get LowerBound --- ///
110.     int OccF;{
111.         int L = 0 ,R = n - 1;
112.         while( L <= R ){
113.             int Mid = (L + R) >> 1;
114.
115.             string SubSuffString = SubStr(s ,Suff[Mid] ,m);
116.
117.                  if( SubSuffString >= t ) R = Mid - 1;
118.             else if( SubSuffString <  t ) L = Mid + 1;
119.         }
120.
121.         string  SubSuffString = SubStr(s ,Suff[L] ,m);
122.         OccF = (SubSuffString == t) ? L : -1;
123.     }
124.
125.     /// --- Binary Search The Suffixes Get UpperBound --- ///
126.     int OccL;{
127.         int L = 0 ,R = n - 1;
128.         while( L <= R ){
129.             int Mid = (L + R) >> 1;
130.
131.             string SubSuffString = SubStr(s ,Suff[Mid] ,m);
132.
133.                  if( SubSuffString >  t ) R = Mid - 1;
134.             else if( SubSuffString <= t ) L = Mid + 1;
135.         }
136.
137.         string  SubSuffString = SubStr(s ,Suff[R] ,m);
138.         OccL = (SubSuffString == t) ? R : -2;
139.     }
140.
141.     int Cnt = OccL - OccF + 1;
142.     /// --- Ans = Idx OF UpperBound - Idx Of LowerBound + 1 --- ///
143.     return Cnt;
144. }
145.
146. int main() {
147.     n = (int)(s = Read() + '\$').size();
148.
149.     vector< int > Suff = ConstructSA(s ,n);
150.
151.     for(int i = 0 ; i < n ; i++ , puts("")){
152.         printf("%d %d " ,i ,Suff[i]);
153.         for(auto i : s.substr(Suff[i]))
154.             printf("%c" ,i);
155.     }
156. }
157.