##基本概念 ###什么是后缀 假如你有一个字符串如
"gzyorz"
它的后缀是
"gzyorz"，"zyorz"，"yorz"，"orz"，"rz"，"z"
很简单。 用$suff[i]$表示以第$i$位为开头的后缀。 ###大小比较 给两个字符串，让你比较大小，从头开始，一位一位的比，如果不相等，就比较两个字符的那个字典序比较大，如果一个串已经到结尾了，它们还是相等，那长的那个大。 比如
"aab"和"aac" 第一位'a'='a'，第二位'a'='a',第三位'b'<'c'，所以"aab"<"aac"。 或 "aab"和"aabc" 第一二三位均相等，但"aabc"比"aab"长，所以"aab"<"aabc"。
###后缀数组和名次数组 拿网上一张十分直观的图 
rnak[sa[i]] = i;
sa[rank[i]] = i;
显然，$x$的排名是$y$，那排名是$y$的就是$x$ ##求后缀数组 构造sa数组的方法一般有两种：
- 倍增算法：\(O(nlogn)\)
- DC3算法：\(O(n)\) 这里只讲一下倍增算法。
对于一个后缀$suff[i]$，直接求$rank$比较困难，我们用倍增的思想，成倍的两两合并出所有的后缀，用第$k-1$轮的$rank$推出第$k$轮的$rank$。 我们第$k$轮的$s[i...i+2k]$可以看做是$s[i...i+2]$和$s[i+2^+1...2k]$拼起来的，而这两个长度为$2$的字符串是上一轮处理出来的，我们知道他们的$rank$，这就相当于两组数字(关键字)比较大小，这样，我们就获得了第$k$轮$s[i...i+2k]$的$rank$。 如果$i$位置后没有$2$个字符，就是$s[i...2^]$不能由上面两个字符串拼起来，表明$i+2$大于等于$len$，也就是$suff[i]$这个字符串，直接补0。
所以，我们得到$"aabaaaab"$的$rank$的过程大概就是这样。 
##基数排序 我们每次把子串合并后都要排一次序，如果直接上快排的话，\(O(len log^2 (len))\)，显然不行啊。
这就用到了$O(len)$的基数排序。 所谓基数排序，就是从最低位开始，先按个位排，再排十位，再排百位…… 这里给张图感性理解一下，建议还是深度的学习一下，对下文的代码也好理解。
##代码
代码还是很有必要解释一下的 如果学了基数排序的话还是基本很好理解的。
int fir[N], sce[N], t[N], sa[N];
//fir第一关键字（rank）
//sec第二关键字（sa）
//排名为i的串出现了多少次（桶）
for (int i = 1; i <= len; ++i) ++t[fir[i] = s[i]]; //把每个字符放入桶内
for (int i = 1; i <= num; ++i) t[i] += t[i - 1]; //前缀和一下求当前字符的排名
for (int i = len; i >= 1; --i) sa[t[fir[i]]--] = i;
/* 这里枚举到i位置时，s[i] (fir[i])的排名是t[fir[i]]，那排名为t[fir[i]]的字符串开头的位置显然为i
-> sa[rank[i]] = i
*/
就是第一轮在没有第二关键字的时候把所有的字母排一遍序。 利用前缀和可以快速的定位出每个位置应有的排名。 这里稍微模拟一下应该很好理解。
for (int i = len - k + 1; i <= n; ++i) sec[++cnt] = i;
for (int i = 1; i <= len; ++i) if (sa[i] > k) sec[++cnt] = sa[i] - k;
第一行：因为这一部分的长度小于$k$，所以没有第二关键字，直接排到最前面好了，$sec[i]$记录的是排名第$cnt$的后缀的开头在$i$位置。
第二行：看排名为$i$的后缀的位置是否大于$k$，位置要大于$k$，当前找的字符串是由两个长度为$k$的子串拼起来的，如果$i$位置小于$k$，这个后缀就不能作为第二关键字了。 然后直接把上一轮的$sa$拿过来用就可以了，同时减去一个数后相对排名不变，一定要时刻记住$sec$存的是排名为$cnt$的后缀的位置，我们知道第二关键字排名第$i$的后缀的位置，这样就得到了以第二关键字的排名。
for (int i = 1; i <= num; ++i) t[i] = 0;
for (int i = 1; i <= len; ++i) ++t[fir[i]];
for (int i = 1; i <= num; ++i) t[i] += t[i - 1];
for (int i = len; i >= 1; --i) sa[t[fir[sec[i]]]--] = sec[i], sec[i] = 0;
这个是把第一二关键字总的排名弄出来。 $fir$数组中存的是上次关键字的$rank$，即第一关键字，对$fir$排序就是对第一关键字排序，那第二关键字呢。 因为第一关键字可能对应很多第二关键字(因为有的串可能能是后缀，有的是长度为$2^$的串，可能相同)，我们要在第一关键字相同的情况下排第二关键字，因为第二关键字已经排好，越大的肯定越靠后。 比如$sec[1]=3$,$sec[2]=4$那4位置开始的后缀要比3位置开始的后缀靠后 $sec[i]$是第二关键字排名为$i$的后缀（sa数组定义）。 $fir[sec[i]]$就是排名为$i$的第二关键字对应的第一关键字。 $t[fir[sec[i]]]$就表示当第一关键字相同时，第二关键字较大的这个后缀的排名是多少。 理同上面的基数排序，\(sa[t[fir[sec[i]]]--] = sec[i]\)。
swap(fir, sec);
fir[sa[1]] = 1, cnt = 1;
for (int i = 2; i <= n; ++i)
fir[sa[i]] = (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k] == sec[sa[i - 1] + k]) ? cnt : ++cnt;
if (cnt == len) break;
num = cnt;
这里，在下面更新$fir$的时候$sec$是没有用的，所以swap一下直接把$fir$的值赋值给$sec$，这时$sec$存的就是$fir$了。 $sa[1]$的排名一定是1，然后定义一个值，表示串的"值"。 如果两个字符串的两个关键字完全相等，则新的"值"也相等。 如果所有的值都不一样，就说明排好序了。 关键字的取值范围就发生了变化，变为了$cnt$。
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int num = 122, len;
int fir[N], sec[N], t[N], sa[N];
char s[N];
inline void SA() {
for (int i = 1; i <= num; ++i) t[i] = 0;
for (int i = 1; i <= len; ++i) ++t[fir[i] = s[i]];
for (int i = 1; i <= num; ++i) t[i] += t[i - 1];
for (int i = len; i >= 1; --i) sa[t[fir[i]]--] = i;
for (int k = 1; k <= len; k <<= 1) {
int cnt = 0;
for (int i = len - k + 1; i <= len; ++i) sec[++cnt] = i;
for (int i = 1; i <= len; ++i) if (sa[i] > k) sec[++cnt] = sa[i] - k;
for (int i = 1; i <= num; ++i) t[i] = 0;
for (int i = 1; i <= len; ++i) ++t[fir[i]];
for (int i = 1; i <= num; ++i) t[i] += t[i - 1];
for (int i = len; i >= 1; --i) sa[t[fir[sec[i]]]--] = sec[i], sec[i] = 0;
swap(fir, sec);
fir[sa[1]] = 1, cnt = 1;
for (int i = 2; i <= len; ++i)
fir[sa[i]] = (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k] == sec[sa[i - 1] + k]) ? cnt : ++cnt;
if (cnt == len) break;
num = cnt;
}
}
int main() {
scanf("%s", s + 1);
len = strlen(s + 1);
SA();
for (int i = 1; i <= len; ++i) printf("%d ", sa[i]);
return 0;
}
##最长公共前缀——LCP ###定义 height[i]：表示$suff[sa[i]]$和$suff[sa[i-1]]$的最大公共前缀，也就是排名完后两个相邻的后缀的最长公共前缀。 h[i]：等于$height[rank[i]]$，$suff[i]$和排序后在它前一名的后缀的最长公共前缀。 
##代码
void Getheight() {
int j, k = 0; //目前height数组计算到k
for (int i = 1; i <= len; i++) {
if(k) k--; //由性质得height至少为k-1
int j = sa[fir[i] - 1]; //排在i前一位的是谁
while(s[i + k] == s[j + k]) k++;
height[fir[i]] = k;
}
}
对于一个字符串 定义$LCP(i,j)=lcp(suff(sa[i]),suff(sa[j])$。 1.对任意$1\leq i<j<k\leq n，LCP(I,k)=min{LCP(I,j),LCP(j,k)}$ 2.设$i<j$，\(LCP(i,j)=min\{LCP(k-1,k)|i+1<=k<=j\}\) 而两个排名不相邻的最长公共前缀为排名在它们之间的height的最小值 
京公网安备 11010502036488号