<算法>后缀数组

后缀数组是一个把所有后缀进行了排序的数组，如ababa这个字符串的后缀数组就是[5, 3, 1, 4, 2]，对应后缀：a, aba, ababa, ba, bab

s[i]字符串，从1开始
sa[i]（长度为k的）排名为i的下标
rk[i]（长度为k的）下标为i的排名

先转载一张图（出处见水印）

每次我们有的是rk表示后缀从i开始长度为k的排名，接下来用这个算长度为2k的rk。
关键字为<rk[i], rk[i+k]>

（其实可以理解成我们把长度为k的处理完以后，我们可以获得每个串的ID，ID越大，字典序越靠后，我们把两个ID拼接起来再排序相当于对一个两位数排序）

1. 按第二关键字排序；
2. 在第二关键字基础上对第一关键字排序；
3. 排序结果即为长度为2k的rk。

具体地：

1. 第二关键字是rk[i+k]，我们要处理出来一个数组（假设为tmp），让tmp存储按第二关键字排序以后的下标；
   1. 一些位置的第二关键字为0，具体来说是[n-k+1,n]这一段，那她们就可以先直接扔进tmp中；
   2. 对于其他的点，我们按从小到大的顺序查询sa[i]，如果sa[i] > k，那么sa[i] - k这个下标对应位置的第二关键字就是i，我们这样处理，依次放进tmp中，这样我们就保证了tmp中的下标从小到大第二关键字递增。

   for (int i = n - k + 1; i <= n; ++i)
   tmp[++tmp[0]] = i;
   for (int i = 1; i <= n; ++i)
   if (sa[i] > k)
       tmp[++tmp[0]] = sa[i] - k;
   

2. 处理好了tmp数组后，我们就要遍历这个数组来最终排序，排序结果是：下标按照双关键字排序的结果，正好是sa：

memset(sum, 0, sizeof(sum[0]) * (rk[0] + 1));
for (int i = 1; i <= n; ++i)
    sum[rk[i]] += 1;
for (int i = 2; i <= rk[0]; ++i)
    sum[i] += sum[i - 1];//sum[i]表示rk=i在新的sa里面的最大位置
for (int i = n; i; --i)//所以这里是从n到1
    sa[sum[rk[tmp[i]]]--] = tmp[i];

3. 现在我们处理好了sa，接下来处理rk：

#define is_equal(i, j, k) (rk[i] == rk[j] && rk[i + k] == rk[j + k])
tmp[0] = 1;//存储rk种类数量，也就是后缀的种数
tmp[sa[1]] = 1;//先处理了sa[1]的rk，方便后面循环
for (int i = 2; i <= n; ++i)//所以这里从2开始
    tmp[sa[i]] = is_equal(sa[i], sa[i - 1], k) ?
        //如果sa[i]对应的字符串和已经处理了的字符串相同的话，那sa[i-1]和她一定相同
        tmp[0] : ++tmp[0];
memcpy(rk, tmp, sizeof(tmp[0]) * (n + 1));//这时rk[0]就保存了rk的种数

完整的代码：（把初始化的代码单独拿出来了，如果你看懂了上面的过程，那初始化就很简单了）（模板：（洛谷P3809）后缀数组）

#include <cstdio>
#include <cctype>
#include <cstring>

const int N = 1000000 + 10;

char s[N];
int n, sa[N], rk[N], sum[N], tmp[N];

#define is_equal(i, j, k) (rk[i] == rk[j] && rk[i + k] == rk[j + k])

int main(void)
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)
        rk[i] = s[i], sum[s[i]] += 1;
    for (int i = 2; i <= 128; ++i)
        sum[i] += sum[i - 1];
    for (int i = n; i; --i)
        sa[sum[s[i]]--] = i;
    rk[0] = 128;
    for (int k = 1; k <= n; k <<= 1)
    {
        tmp[0] = 0;
        for (int i = n - k + 1; i <= n; ++i)
            tmp[++tmp[0]] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > k)
                tmp[++tmp[0]] = sa[i] - k;
        memset(sum, 0, sizeof(sum[0]) * (rk[0] + 1));
        for (int i = 1; i <= n; ++i)
            sum[rk[i]] += 1;
        for (int i = 2; i <= rk[0]; ++i)
            sum[i] += sum[i - 1];
        for (int i = n; i; --i)
            sa[sum[rk[tmp[i]]]--] = tmp[i];
        tmp[0] = 1;
        tmp[sa[1]] = 1;
        for (int i = 2; i <= n; ++i)
            tmp[sa[i]] = is_equal(sa[i], sa[i - 1], k) ? tmp[0] : ++tmp[0];
        memcpy(rk, tmp, sizeof(tmp[0]) * (n + 1));
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", sa[i]);
}

再来个height数组，因为SA和这个经常一起用

LCP: 最长公共前缀

height[i]为排名为i的后缀与排名为i-1的后缀的LCP（height[1]=0）

来个~莫名其妙~的结论：
height[rk[i]] \ge height[rk[i - 1]] - 1

1. height[rk[i-1]] < 2，易得
2. height[rk[i-1]] > 1：
   下标为i - 1:aAD(|aA|=\text{height[rk[i-1]]})
   下标为i:AD
   下标为sa[rank[i-1]-1]:aAB
   下标为sa[rank[i]-1]:A[B/C]
   LCP(i, sa[rank[i]-1]):A(X)

for (i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i + k] == s[sa[rank[i] - 1] + k]) ++k;
    height[rank[i]] = k;
}