基础概念：

子串：

在一个字符串s中，取任意i<=j,那么从i到j的这一段就叫做s的一个子串
后缀：

从字符串s的某个位置i到字符串末尾的子串，
suff[i]:

以s的第i个字符为第一个元素的后缀
后缀数组：
现有字符串s，长度为n
把s的全部后缀按照字典序排序，总共有n个后缀
sa[i]:

表示排名为i的后缀的起始位置的下标——根据排名来查询后缀起始位置
rak[i]:

表示起始位置为i的后缀的排名——根据起始位置来查询后缀排名

LCP:
LCP[i][j]:表示suff[sa[i]](排名为i的后缀)与suff[sa[j]]（排名为j的后缀）的最长公共前缀的长度
LCP[i][j]=LCP[j][j]
LCP[i][i]=Len[sa[i]]=n-sa[i]+1;
该式子的意思为，自身与自身的最长公共前缀就是自身，其长度为排名为i的后缀的长度，而其长度等于n减去起始位置的下标再加1
LCP性质:
当i<j<k时
LCP[i][j]>=LCP[i][k]
显然由字典序排序的单调性可知，离i越近的后缀与i的前缀重合度就会越大，即长度越长

Height[i]:

表示LCP[i][i-1]，即排名为i的后缀与排名为i-1的后缀的最长公共前缀

后缀数组实现：DC3 O(n)
                         DA O(nlogn)

倍增实现：

倍增思路：
对以每个字符为开头的长度为2^k的子字符串进行排序，即为rank值
k从0开始，每次+1
当2^k的长度大于n以后
以第一个字符开头的长度为2^k的子字符串已经包含了整个字符串
所以每个字符开始的长度为2^k的子字符串就相当于所有的后缀
对于靠后的起始字符的子串而言，若其到字符串末尾的长度小于2^k，那么就取它的实际长度
并且我们对这些子字符串都已经用一定的方法比较出了大小
即rank值里面没有相同的值
那么此时的rank值就是最后的结果

那么如何得到这个rank值呢？
我们利用倍增的思想
我们对于n个长度为2^k的子字符串进行rank值排序
当k等于0的时候，子串长度为1，直接按照字典序排出rank值大小即可
假设我们要比较a和b两个长度为2^k的子字符串
只需要将其划分成为两个2^(k-1)长度的子字符串
即，将a划分为a1和a2，将b划分为b1和b2，长度均为2^(k-1)
那么我们先比较a1和b1的rank值大小
若rank[a1]!=rank[a2],则已经比较出a和b的字典序大小
若rank[a1]==rank[a2]，我们再进而比较a2和b2的rank值
由于两个子串rank值不可能相同，则一定能够通过rank[a2]和rank[b2]比较出a和b的大小
这样，当2^k>n时，我们就得到了sa数组

后缀数组的应用举例：

后缀数组为排序后的数组，具有一定的单调性

求无重复子串：

对于一个长度为n的字符串而言，其最多有n*(n+1)/2个不重复子串
思考过程：
对于每一个子串，我们可以分其以不同的起始位置讨论
以下标为1的开头的子串有n个
以下标为2的开头的子串有n-1个
以此类推
最后就是一个1+2+3+……+n的求和
故有n*(n+1)/2个子串
对于s中的每一个子串
一定存在于每一个后缀的前缀中
即每一个后缀的前缀都会是一个子串
那么我们只需要将重复的前缀剔除，剩余的后缀所贡献的前缀的总和就是无重复子串的个数
由于字典序排序问题
相邻的两个后缀的前缀重合度一定是最大的

即对于排名为i的后缀而言
其能贡献的子串个数为n-sa[i]+1-Height[i]

求可重叠的k次最长重复子串
由上面第一道题的讨论已知
每一个子串一定存在于每一个后缀的前缀中
那么要求可重复的子串
就是求后缀数组中可重复的前缀
这就是height数组的含义

由于按字典序排序后
后缀的前缀重叠度最大
当i<j<k时
LCP[i][j]>=LCP[i][k]
因此选一个连续的区间的前缀
他们的可重叠度是最大的
单调性——二分——枚举最长长度

模版代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;//将待排序的字符串放到r数组中
//从r[0]到r[n-1]，长度为n
//且最大值小于<M
//并约定除了r[n-1]外的r[i]都大于0，且r[n-1]=0
//函数结束后，再把结果放到sa数组中，范围从sa[0]到sa[n-1]
int wa[N], wb[N], wv[N], wss[N], cal[N], n, sa[N];
char s[N];
int cmp(int *r, int a, int b, int l)
{return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int M)
{int i, j, p, *x = wa, *y = wb, *t;//由于r[i]的最大值不会很大，所以这里采用基数排序//如果r[i]的最大值很大，可以改为快速排序//基数排序for (i = 0; i < M; i++)wss[i] = 0;//令计数初值为0for (i = 0; i < n; i++)wss[x[i] = r[i]]++;//给x数组赋初值为r,并令r[i]对应的wss加1for (i = 1; i < M; i++)wss[i] += wss[i - 1];//前缀和,求出r[i]的字母前共有几个字母for (i = n - 1; i >= 0; i--)sa[--wss[x[i]]] = i;//wss[x[i]]就表示是x[i]前有几个字母，同时也是x[i]字母的排名+1//那么sa[--wss[x[i]]]就是x[i]也就是r[i]的排名所对应的起始字母的位置，也就是i//若干次基数排序//j为当前处理子串长度//数组y保存对第二关键字排序的结果//也就是y[i]表示第二关键字排名为i的起始字母的位置//然后对第一关键字排序for (j = 1, p = 1; p < n; j *= 2, M = p){//第一次基数排序//对第二关键字排序for (p = 0, i = n - j; i < n; i++)//i会加j次，p也会加到jy[p++] = i;for (i = 0; i < n; i++)//总共会有n-j个y满足sa[i]>=j//加上前面有j个y//y数组总共的长度为n//当排名为i的子串的起始位置大于等于j的时候//说明他会被前面的长度为j的子串接上，也就是说它有可能成为第二关键值，因此需要求出他的第二关键值的排名//又由于长度小于j的子串的y分别被初始化为n-j,n-j+1......n-1//那么长度大于等于j的子串的起始位置再重新记作0,1,2,3......//这样一来，对于上次得到的sa的排名来说//长度小于j的子串从第0排到第j-1//长度大于等于j的子串的相对排名不变，且连续在一起，分别从第n-j-1排到第n-1if (sa[i] >= j)y[p++] = sa[i] - j;//y数组保存对第二关键字排序的结果//第二次基数排序//对第一关键字排序for (i = 0; i < n; i++)wv[i] = x[y[i]];//wv[i]表示第二关键值排名为i的字母的关键字的值（即第一关键字的值）for (i = 0; i < M; i++)wss[i] = 0;for (i = 0; i < n; i++)wss[wv[i]]++;for (i = 1; i < M; i++)wss[i] += wss[i - 1];for (i = n - 1; i >= 0; i--)sa[--wss[wv[i]]] = y[i];//排名为--wss[wv[i]]的后缀的起始位置为y[i]//计算rank数组//更新rank值//首先交换x数组和y数组//更新排名从0到n-1的rank//由于rank会有重复的，所以要比较一下sa[i-1]和sa[i]的rank是否相同//相同的话,x[sa[i]]和x[sa[i-1]]的值就应该相同，所以取p-1//否则的话不同，取p，且p递增for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;}return;
}int rak[N], height[N];
// 获取height数组
void calheight(int *r, int *sa, int n)
{int i, j, k = 0;//先初始化rank数组for (i = 1; i <= n; i++) rak[sa[i]] = i;//k为最长公共前缀长度//初始化为0//这里的O(n)算法运用到性质height[i]>=height[i-1]-1for (i = 0; i < n; height[rak[i++]] = k) for (k ? k-- : 0, j = sa[rak[i] - 1]; r[i + k] == r[j + k]; k++);// k是否存在？// k存在就递减1// j等于以第i个字母起始的后缀的前一个排名的后缀的起始字母的位置// 如果以第i个字母往后第k个也和以第j个字母往后第k个相同，那么k++，继续循环，直到找到不同的字母// 那么k就是sa[rak[i]]与sa[rak[i]-1]的最长公共前缀的长度// 最后将height[rak[i]]的值更新为k（也就是外层循环的for的第三个语句）for (int i = n; i; i--) rak[i] = rak[i - 1], sa[i]++;
}
int main()
{int cas = 1;while (~scanf("%s", s + 1)){n = strlen(s + 1);for (int i = 1; i <= n; i++)cal[i] = s[i];cal[n + 1] = 0;da(cal + 1, sa, n + 1, 200);calheight(cal + 1, sa, n);for (int i = 1; i <= n; i++){printf("%d ", height[i]);}puts("");for (int i = 1; i <= n; i++){printf("%d ", sa[i]);}puts("");for (int i = 1; i <= n; i++){printf("%d ", rak[i]);}puts("");}
}