算法
(后缀数组) $\mathcal{O}(N)$
SA-IS
(Suffix Array Induce Sort) 是一种效率高常数小的后缀数组构建算法
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
template <class Str>
struct SA {
Str s;
vector<int> sa, rsa, lcp;
SA() {}
SA(Str _s, vector<int> _sa) : s(_s), sa(_sa) {
int n = int(s.size());
// make rsa
rsa = vector<int>(n + 1);
for (int i = 0; i <= n; i++) {
rsa[sa[i]] = i;
}
// make lcp
lcp = vector<int>(n);
int h = 0;
for (int i = 0; i < n; i++) {
int j = sa[rsa[i] - 1];
if (h > 0) h--;
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rsa[i] - 1] = h;
}
}
};
template <class Str>
vector<int> sa_is(Str s, int B = 200) {
int n = int(s.size());
vector<int> sa(n + 1);
if (n == 0) return sa;
for (int i = 0; i < n; i++) s[i]++;
s.push_back(0);
B++;
vector<bool> ls(n + 1);
ls[n] = true;
for (int i = n - 1; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
vector<int> sum_l(B + 1), sum_s(B + 1);
for (int i = 0; i <= n; i++) {
if (!ls[i])
sum_s[s[i]]++;
else
sum_l[s[i] + 1]++;
}
for (int i = 0; i < B; i++) {
sum_l[i + 1] += sum_s[i];
sum_s[i + 1] += sum_l[i + 1];
}
auto induce = [&](const vector<int>& lms) {
fill(begin(sa), end(sa), -1);
auto buf0 = sum_s;
for (auto d : lms) {
sa[buf0[s[d]]++] = d;
}
auto buf1 = sum_l;
for (int i = 0; i <= n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf1[s[v - 1]]++] = v - 1;
}
}
auto buf2 = sum_l;
for (int i = n; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf2[s[v - 1] + 1]] = v - 1;
}
}
};
vector<int> lms, lms_map(n + 1, -1);
for (int i = 1; i <= n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = int(lms.size());
lms.push_back(i);
}
}
induce(lms);
if (lms.size() >= 2) {
int m = int(lms.size()) - 1;
vector<int> lms2;
for (int v : sa) {
if (lms_map[v] != -1) lms2.push_back(v);
}
int rec_n = 1;
vector<int> rec_s(m);
rec_s[lms_map[lms2[1]]] = 1;
for (int i = 2; i <= m; i++) {
int l = lms2[i - 1], r = lms2[i];
int nl = lms[lms_map[l] + 1], nr = lms[lms_map[r] + 1];
if (nl - l != nr - r)
rec_n++;
else {
while (l <= nl) {
if (s[l] != s[r]) {
rec_n++;
break;
}
l++;
r++;
}
}
rec_s[lms_map[lms2[i]]] = rec_n;
}
vector<int> nx_lms;
auto ch_sa = sa_is(rec_s, rec_n);
for (int d : ch_sa) {
nx_lms.push_back(lms[d]);
}
induce(nx_lms);
}
return sa;
}
int main() {
static char buf[1'000'005];
string s;
scanf("%s", buf);
s = buf;
SA<string> sa(s, sa_is(s));
auto ans = sa.sa;
for (int i = 1; i < ans.size(); ++i) {
cout << ans[i]+1 << ' ';
}
return 0;
}
洛谷
Orz