Skip to content

Commit 3aada74

Browse files
yosupo06yosupo06
committed
add suffixarray(log^2)
1 parent f32707c commit 3aada74

2 files changed

Lines changed: 169 additions & 139 deletions

File tree

‎Cpp/String/SAIS.h‎

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
/**
2+
* Suffix Array
3+
*/
4+
5+
namespace SuffixArray {
6+
template<class T>
7+
void induce(int n, const T s[], bool ls[], int sa[], int l_basm[], int B) {
8+
int buf[B+10];
9+
copy_n(l_basm, B+1, buf);
10+
for (int i = 0; i <= n; i++) {
11+
if (sa[i] >= 1 && !ls[sa[i]-1]) {
12+
int bc = s[sa[i]-1];
13+
sa[buf[bc]++] = sa[i]-1;
14+
}
15+
}
16+
17+
copy_n(l_basm, B+1, buf);
18+
for (int i = n; i > 0; i--) {
19+
if (sa[i] >= 1 && ls[sa[i]-1]) {
20+
int bc = s[sa[i]-1];
21+
sa[--buf[bc+1]] = sa[i]-1;
22+
}
23+
}
24+
}
25+
26+
template<class T>
27+
void SA(int n, const T s[], int sa[], int B = 200) {
28+
bool ls[n+1]; //L:false S:true
29+
int l_ba[B+1], s_ba[B+1];
30+
fill_n(l_ba, B+1, 0); fill_n(s_ba, B+1, 0);
31+
ls[n] = true;
32+
for (int i = n-1; i >= 0; i--) {
33+
if (i == n-1 || s[i] > s[i+1]) {
34+
ls[i] = false;
35+
} else if (s[i] < s[i+1]) {
36+
ls[i] = true;
37+
} else {
38+
ls[i] = ls[i+1];
39+
}
40+
if (!ls[i]) {
41+
l_ba[(int)s[i]]++;
42+
} else {
43+
s_ba[(int)s[i]]++;
44+
}
45+
}
46+
47+
vector<int> v;
48+
int lms[n+1];
49+
fill_n(lms, n+1, -1);
50+
int c = 0;
51+
for (int i = 1; i < n; i++) {
52+
if (!ls[i-1] && ls[i]) {
53+
lms[i] = c++;
54+
v.push_back(i);
55+
}
56+
}
57+
58+
int l_basm[B+1], s_basm[B+1];
59+
l_basm[0] = 1; s_basm[0] = 1+l_ba[0];
60+
for (int i = 1; i <= B; i++) {
61+
l_basm[i] = s_basm[i-1]+s_ba[i-1];
62+
s_basm[i] = l_basm[i]+l_ba[i];
63+
}
64+
65+
if (v.size()) {
66+
vector<int> v2 = v;
67+
int buf[B+1];
68+
copy_n(s_basm, B+1, buf);
69+
fill_n(sa, n+1, -1);
70+
sa[0] = n;
71+
for (int i = 0; i < (int)v.size(); i++) {
72+
int c = s[v[i]];
73+
sa[buf[c]++] = v[i];
74+
}
75+
induce(n, s, ls, sa, l_basm, B);
76+
int c = 0;
77+
for (int i = 1; i <= n; i++) {
78+
if (lms[sa[i]] == -1) continue;
79+
v[c++] = sa[i];
80+
}
81+
82+
int s2[v.size()];
83+
int sa2[v.size()+1];
84+
c = 0;
85+
s2[lms[v[0]]] = 0;
86+
for (int i = 1; i < (int)v.size(); i++) {
87+
int l = v[i-1], r = v[i];
88+
while (true) {
89+
if (s[l] != s[r]) {
90+
c++;
91+
break;
92+
}
93+
l++; r++;
94+
if (lms[l] != -1 || lms[r] != -1) {
95+
if (lms[l] == -1 || lms[r] == -1) {
96+
c++;
97+
}
98+
break;
99+
}
100+
}
101+
s2[lms[v[i]]] = c;
102+
}
103+
SA(v.size(), s2, sa2, c);
104+
for (int i = 1; i <= (int)v.size(); i++) {
105+
v[i-1] = v2[sa2[i]];
106+
}
107+
}
108+
109+
int buf[B+1];
110+
copy_n(s_basm, B+1, buf);
111+
112+
fill_n(sa, n+1, -1);
113+
sa[0] = n;
114+
for (int i = 0; i < (int)v.size(); i++) {
115+
int c = s[v[i]];
116+
sa[buf[c]++] = v[i];
117+
}
118+
119+
induce(n, s, ls, sa, l_basm, B);
120+
}
121+
122+
template <class T>
123+
void LCP(int n, const T s[], const int sa[], int lcp[]) {
124+
int rsa[n+1];
125+
for (int i = 0; i <= n; i++) {
126+
rsa[sa[i]] = i;
127+
}
128+
int h = 0;
129+
for (int i = 0; i < n; i++) {
130+
int j = sa[rsa[i]-1];
131+
132+
if (h > 0) h--;
133+
for (; j+h < n && i+h < n; h++) {
134+
if (s[j+h] != s[i+h]) break;
135+
}
136+
lcp[rsa[i]-1] = h;
137+
}
138+
}
139+
}

‎Cpp/String/SuffixArray.h‎

Lines changed: 30 additions & 139 deletions
Original file line numberDiff line numberDiff line change
@@ -1,139 +1,30 @@
1-
/**
2-
* Suffix Array
3-
*/
4-
5-
namespace SuffixArray {
6-
template<class T>
7-
void induce(int n, const T s[], bool ls[], int sa[], int l_basm[], int B) {
8-
int buf[B+10];
9-
copy_n(l_basm, B+1, buf);
10-
for (int i = 0; i <= n; i++) {
11-
if (sa[i] >= 1 && !ls[sa[i]-1]) {
12-
int bc = s[sa[i]-1];
13-
sa[buf[bc]++] = sa[i]-1;
14-
}
15-
}
16-
17-
copy_n(l_basm, B+1, buf);
18-
for (int i = n; i > 0; i--) {
19-
if (sa[i] >= 1 && ls[sa[i]-1]) {
20-
int bc = s[sa[i]-1];
21-
sa[--buf[bc+1]] = sa[i]-1;
22-
}
23-
}
24-
}
25-
26-
template<class T>
27-
void SA(int n, const T s[], int sa[], int B = 200) {
28-
bool ls[n+1]; //L:false S:true
29-
int l_ba[B+1], s_ba[B+1];
30-
fill_n(l_ba, B+1, 0); fill_n(s_ba, B+1, 0);
31-
ls[n] = true;
32-
for (int i = n-1; i >= 0; i--) {
33-
if (i == n-1 || s[i] > s[i+1]) {
34-
ls[i] = false;
35-
} else if (s[i] < s[i+1]) {
36-
ls[i] = true;
37-
} else {
38-
ls[i] = ls[i+1];
39-
}
40-
if (!ls[i]) {
41-
l_ba[(int)s[i]]++;
42-
} else {
43-
s_ba[(int)s[i]]++;
44-
}
45-
}
46-
47-
vector<int> v;
48-
int lms[n+1];
49-
fill_n(lms, n+1, -1);
50-
int c = 0;
51-
for (int i = 1; i < n; i++) {
52-
if (!ls[i-1] && ls[i]) {
53-
lms[i] = c++;
54-
v.push_back(i);
55-
}
56-
}
57-
58-
int l_basm[B+1], s_basm[B+1];
59-
l_basm[0] = 1; s_basm[0] = 1+l_ba[0];
60-
for (int i = 1; i <= B; i++) {
61-
l_basm[i] = s_basm[i-1]+s_ba[i-1];
62-
s_basm[i] = l_basm[i]+l_ba[i];
63-
}
64-
65-
if (v.size()) {
66-
vector<int> v2 = v;
67-
int buf[B+1];
68-
copy_n(s_basm, B+1, buf);
69-
fill_n(sa, n+1, -1);
70-
sa[0] = n;
71-
for (int i = 0; i < (int)v.size(); i++) {
72-
int c = s[v[i]];
73-
sa[buf[c]++] = v[i];
74-
}
75-
induce(n, s, ls, sa, l_basm, B);
76-
int c = 0;
77-
for (int i = 1; i <= n; i++) {
78-
if (lms[sa[i]] == -1) continue;
79-
v[c++] = sa[i];
80-
}
81-
82-
int s2[v.size()];
83-
int sa2[v.size()+1];
84-
c = 0;
85-
s2[lms[v[0]]] = 0;
86-
for (int i = 1; i < (int)v.size(); i++) {
87-
int l = v[i-1], r = v[i];
88-
while (true) {
89-
if (s[l] != s[r]) {
90-
c++;
91-
break;
92-
}
93-
l++; r++;
94-
if (lms[l] != -1 || lms[r] != -1) {
95-
if (lms[l] == -1 || lms[r] == -1) {
96-
c++;
97-
}
98-
break;
99-
}
100-
}
101-
s2[lms[v[i]]] = c;
102-
}
103-
SA(v.size(), s2, sa2, c);
104-
for (int i = 1; i <= (int)v.size(); i++) {
105-
v[i-1] = v2[sa2[i]];
106-
}
107-
}
108-
109-
int buf[B+1];
110-
copy_n(s_basm, B+1, buf);
111-
112-
fill_n(sa, n+1, -1);
113-
sa[0] = n;
114-
for (int i = 0; i < (int)v.size(); i++) {
115-
int c = s[v[i]];
116-
sa[buf[c]++] = v[i];
117-
}
118-
119-
induce(n, s, ls, sa, l_basm, B);
120-
}
121-
122-
template <class T>
123-
void LCP(int n, const T s[], const int sa[], int lcp[]) {
124-
int rsa[n+1];
125-
for (int i = 0; i <= n; i++) {
126-
rsa[sa[i]] = i;
127-
}
128-
int h = 0;
129-
for (int i = 0; i < n; i++) {
130-
int j = sa[rsa[i]-1];
131-
132-
if (h > 0) h--;
133-
for (; j+h < n && i+h < n; h++) {
134-
if (s[j+h] != s[i+h]) break;
135-
}
136-
lcp[rsa[i]-1] = h;
137-
}
138-
}
139-
}
1+
template<int N>
2+
struct SA {
3+
static int n, k;
4+
static int rank[N+1], tmp[N+1];
5+
6+
static bool com(int i, int j) {
7+
if (rank[i] != rank[j]) return rank[i] < rank[j];
8+
int ri = i+k <= n ? rank[i+k] : -1;
9+
int rj = j+k <= n ? rank[j+k] : -1;
10+
return ri < rj;
11+
}
12+
13+
void con(string S, int *sa) {
14+
int n = (int)S.size();
15+
for (int i = 0; i <= n; i++) {
16+
sa[i] = i;
17+
rank[i] = i < n ? S[i] : -1;
18+
}
19+
for (k = 1; k <= n; k *= 2) {
20+
sort(sa, sa+n+1, com);
21+
tmp[sa[0]] = 0;
22+
for (int i = 1; i <= n; i++) {
23+
tmp[sa[i]] = tmp[sa[i-1]] + (com(sa[i-1], sa[i]) ? 1 : 0);
24+
}
25+
for (int i = 0; i <= n; i++) {
26+
rank[i] = tmp[i];
27+
}
28+
}
29+
}
30+
};

0 commit comments

Comments
 (0)