定义
\(sa[i]\)：字典序第\(i\)小的后缀（suffix array）
\(ra[i]\)：后缀\(str[i...n]\)在\(sa\)中的下标（rank）
思路
假定字符串长度为\(n\)，它必然是一个2的幂（不足就认为后面是空）
后缀数组\(sa[i]\)可认为是长为\(n\)的情况下字典序第\(i\)小的子串\(sa_n[i]\)（不足就认为后面是空）
它可以通过长度为\(n/2\)的字典序\(sa_{n/2}[i]\)（以及当前的\(ra\)）的所有情况来\(O(1)\)判断得出
（也就是说对于\(str[i,i+2^j)\)可通过\(str[i,i+2^{j/2})\)和\(str[i+2^{j/2},i+2^j)\)的关键字组合得出）
因此\(sa[i,n]\)的集合可通过\(sa_1[i],sa_2[i],sa_4[i] \dots sa_{n/2}[i]\)各个集合来倍增递推得出
所以倍增法的最优实现复杂度是\(O(nlogn)\)
（当前介绍的具体实现是基于快排的\(O(nlog^2n)\)）
具体过程
举个例子
\[str=ababaaab\] \[n = 8\]我们认为最小的合法字典序为0，空子串的字典序为-1
通过自下而上的先从\(ra_0[i]\)算起
其中横坐标代表\(i\),空使用\(X\)来表示
每一次迭代的\(str\)是表示\(str[i,i+2^j)\)的字串
（比如\(j=2\)时的\(str\)中从0数起第5个串表示为\(aabX\)，既\(str[5,9)\)）
我们保证不可能存在\(ra\)出现第一关键字为-1的情况
j = 0
[str] a b a b a a a b
[ra0] 0 1 0 1 0 0 0 1
j = 1
[str] (a,b) (b,a) (a,b) (b,a) (a,a) (a,a) (a,b) (b,X)
[ra0] (0,1) (1,0) (0,1) (1,0) (0,0) (0,0) (0,1) (1,-1)
[ra1] 1 3 1 3 0 0 1 2
j = 2
[str] (ab,ab) (ba,ba) (ab,aa) (ba,aa) (aa,ab) (aa,bX) (ab,XX) (bX,XX)
[ra1] (1,1) (3,3) (1,0) (3,0) (0,1) (0,2) (1,-1) (2,-1)
[ra2] (4) (7) (3) (6) (0) (1) (2) (5)
j = 3
[str] (abab,aaab) (baba,aabX) (abaa,abX) (baaa,bX) (aaab,X) (aabX,X) (abX,X) (bX,X)
[ra2] (4,0) (7,1) (3,2) (6,5) (0,-1) (1,-1) (2,-1) (5,-1)
[ra3] (4) (7) (3) (6) (0) (1) (2) (5)
（其实可以看出，当第一关键字互不相同时，已经不需要再多余递推下去了，这种优化策略在大量随机串很大幅度提高效率，比如\(str = hfkdjfhkjsfhdksja\)只需计算一遍）
如果需要倍增法最优的实现，可参考国家集训队大佬给出的基数排序版本
也有\(O(n)\)实现的SA-IS算法，不过我没了解过
定义2
我们为\(sa\)数组衍生另外两个定义
\(hgt[i]\)：后缀\(str[sa[i]...]\)与\(str[sa[i-1]...]\)的最长公共前缀（height）
\(LCP(i,j)\)：后缀\(str[sa[i]...]\)和\(str[sa[j]...]\)的最长公共前缀
思路2
设\(j=sa[ra[i]-1]\)
当依次计算\(str[i...]\)和\(str[j...]\)(对应\(i\)在\(sa\)数组上的前一个后缀)
如果已经得知\(h[i]=hgt[ra[i]]\)（表明\(str[i]\)和\(str[j]\)的最多前\(h[i]\)个字符相同）
而对比之下\(str[i+1]\)和\(str[j+1]\)则分别对应于前面砍掉了首字符，所以至少前\(h[i]-1\)个字符相同，\(h[i+1] \ge h[i]-1\)，对于该串只需从下标\(h[i]-1\)开始判断即可
因此求出\(hgt\)数组的复杂度是\(O(n)\)
如果对于两个串\(str[i...]\)和\(str[j...]\)且满足\(ra[i] < ra[j]\)
由于\(i\)和\(j\)排名不相邻（相邻就直接是\(hgt\)了，其结果肯定不会比\(sa\)当中对应\(i\)到\(j\)的\(hgt\)更优
由\(hgt\)的传递性可以得出结论
\[LCP(i,j) = min(hgt[ra[i]+1],hgt[ra[i]+2],...,hgt[ra[j]])\]这一部分用\(RMQ\)预处理后即可\(O(1)\)求解任意\(LCP(i,j)\)
举例2
ababaaab
h[i] str[i] str[j]
3 ababaaab abaaab
2 babaaab baaab(注意这和上一个str[j+1]没有关系)
2 abaaab ab
1 baaab b
0 aaab
2 aab aaab
1 ab aab
0 b ababaaab
完成版
#include<bits/stdc++.h>
#define fast_io() do{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}while(0)
#define print(a) printf("%a",(ll)(a))
#define printbk(a) printf("%lld ",(ll)(a))
#define println(a) printf("%lld\n",(ll)(a))
#define rep(i,j,k) for(int i = (j); i <= (k); ++i)
#define rrep(i,j,k) for(int i = (j); i >= (k); --i)
#define erep(i,u,v) for(int i = head[u], v = to[i]; ~i; v = to[i = nxt[i]])
#define mod(a,b) (((a)%b+b)%b)
#define int int_fast32_t
using namespace std;
using ll = long long;
const int MAXN = 1e5+11;
struct SA {
string str;
int n;
vector<int> sa,ra,tmp,hgt;
void build(const string &s,bool lcp = false) {
str = s;
n = s.length();
sa = ra = tmp = vector<int>(n);
for(int i = 0; i < n; i++) {
sa[i] = i;
ra[i] = str[i];
}
auto k = 0;
auto cmp = [&](int i,int j) -> bool {
if(ra[i] != ra[j]) return ra[i] < ra[j];
int ri = i+k < n ? ra[i+k] : -1;
int rj = j+k < n ? ra[j+k] : -1;
return ri < rj;
};
for(k = 1; k <= n; k <<= 1) {
sort(sa.begin(),sa.end(),cmp);
tmp[sa[0]] = 0;
for(int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i-1]]+cmp(sa[i-1],sa[i]); // 依靠ra的结果,不能覆盖
}
auto flag = false;
for(auto i = 0; i < n; i++) {
ra[i] = tmp[i];
if(ra[i] == n-1) flag = true; // opt
}
if(flag) break; // opt
}
if(!lcp) return;
hgt = vector<int>(n);
int h = 0;
for(int i = 0; i < n; i++) {
if(ra[i]-1 < 0) { // 有溢出风险
hgt[ra[i]] = h = 0;
continue;
}
int j = sa[ra[i]-1];
if(h) h--;
for(int t=max(i,j); t+h < n; h++) {
if(str[i+h]!=str[j+h]) break;
}
hgt[ra[i]] = h;
}
}
}sa;
int32_t main() {
fast_io();
string s;
cin >> s;
sa.build(s,1);
for(int i = 0; i < sa.str.length(); i++) {
cout << sa.hgt[sa.ra[i]] << " ";
cout << sa.str.substr(i) << " " << (sa.ra[i]-1 < 0 ? " " : sa.str.substr(sa.sa[sa.ra[i]-1])) << endl;
}
return 0;
}
Q：如何验证你的算法正确性？
A：https://www.luogu.com.cn/problem/P3809
更多查询：https://zhuanlan.zhihu.com/p/28331415