子串：从原串中选取连续的一段，即子串
空串也是子串
后缀：suf(k)为s(k....n)构成的子串
任何子串都是某个后缀的前缀
最长公共前缀 lcp(suf(i),suf(j))
问题：
将所有后缀suf(1),suf(2),suf(N)按照字典序从小到大排序
暴力sort N^2^ logN
二分+hash :
Nlog^2^N
cmp函数中二分suf(i)和suf(j)的lcp
return s[i+|lcp|] < s[j+|lcp|]
------- 以上为暴力做法
进入正文：
SA[1]排序第1的后缀的开始位置
Rank[i]=后缀suf(i)的排名
Rank[sa[l]] = l
sa[Rank[i]] = i
求sa然后得到rank
倍增
sub[i][k]：s从i开始长度为 2^k^的子串
sub[i][k] = s[i....i+(1<<k)-1 ],超过N的部分都视为'\0'(字典序最小符号)
rank[i][k]=sub[i][k]在长度2^k^的所有子串中的排名
sa[1][k] :在长度2^k^的所有子串中排名第1的子串的开始位置
step 1：先求sub[1][0],sub[2][0],.......,sub[N][0]的字典排序
先求长度为1的子串，然后看字典序是多少
再求2,4，8，N，
当子串长度2^k^>=N时，子串排序就是后缀排序
利用rank[i....N][k],如何求出rank[1...N][k+1]
二分比较，
对于两个子串sub[i][k+1]与sub[j][k+1]比较
先比较rank[i][k]与rank[j]k
如果相等再比较rank[i+2^k^]与rankj+2^k^
相当于二元组（第一关键字-->rank[i][k],第二-->rank[i+2^k^][k]）排序
注意rank[i][k]值域是不超过N的正整数，可以用基数排序（桶排序）
基础排序：先按second，再按照first
复杂度O(Nd) d是最大位数，此处d是2，（因为两个关键词）
写SA时用cnt数组实现
将a[i]数组（1~N）基数排序，结果存放在sa数组中
sa[1]：排名第1th的数在a中的下标
for(int i=1;i<=N;i++)cnt[a[i]++;//桶排 for(int i=1;i<=N;i++)cnt[i]+=cnt[i-1];//求前缀和 for(int i=N;i;i--)sa[cnt[a[i]]--]=i;//sa[cnt[a[i]]]=i,cnt[a[i]]--;
a=[2,1,2,4,2]
cnt=[1,3,0,1,0]
cnt=[1,4,4,5,5]
大致过程：
for k = 1 ~ logN
按rank[i+2^k^][k]基数排序(第二关键字)
按照rank[i][k]基数排序，（第一关键字）
得到sa[i][k+1]数组
由sa[i][k+1]求出rank[i][k+1]
动画链接
数据结构和算法动态可视化 (Chinese)
sa--->rank
rk[i]中有并列
for(p=0;i=1;i<=n;i++)
{
if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+k]==oldrk[sa[i-1]+k])rk[sa[i]]=p;
else rk[sa[i]]=++p;
} 
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1000010;
char s[N];
int n, sa[N], rk[N << 1], oldrk[N << 1], id[N], cnt[N];
int main() {
int i, m, p, w;
scanf("%s", s + 1);
n = strlen(s + 1);
m = max(n, 300);
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;//基数排序
for (w = 1; w < n; w <<= 1) {//倍增
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i) id[i] = sa[i];
for (i = 1; i <= n; ++i) ++cnt[rk[id[i] + w]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[id[i] + w]]--] = id[i];
//上面为第二部分基数排序，下面为第二部分基数排序
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i) id[i] = sa[i];
for (i = 1; i <= n; ++i) ++cnt[rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i];
memcpy(oldrk, rk, sizeof(rk));
for (p = 0, i = 1; i <= n; ++i) {
if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
rk[sa[i]] = p;
} else {
rk[sa[i]] = ++p;
}//由sa得到新的rank数组
}
}
for (i = 1; i <= n; ++i) printf("%d ", sa[i]);
return 0;
} 这个代码会超时，经过优化后：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1000010;
char s[N];
int n, sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];
// px[i] = rk[id[i]]（用于排序的数组所以叫 px）
bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
int main() {
int i, m = 300, p, w;
scanf("%s", s + 1);
n = strlen(s + 1);
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
for (w = 1; w < n; w <<= 1, m = p) { // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
memcpy(oldrk, rk, sizeof(rk));
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
for (i = 1; i <= n; ++i) printf("%d ", sa[i]);
return 0;
} 要求全文背诵
复杂度为O(n logn)
京公网安备 11010502036488号