后缀数组模板代码（我想了好几天的一个我自己能看懂的算法解释）.md

首先，求后缀数组网上都是用的倍增法，如https://blog.csdn.net/a1035719430/article/details/80217267 但是

网上的博客真的妈的都是狗屎！！！！！！！只讲了倍增法的概念但是从来不讲模板代码的思路。。。

我花了一天时间终于才搞清楚了模板代码的思路。。。 模板代码主要的技巧在于:

用副位次序更新主位次序（即SA）

以字符串"aaaaaaaa"为例

        1   2   3   4   5   6   7   8       a   a   a   a   a   a   a   a
sa[i]   1   2   3   4   5   6   7   8       a   a   a   a   a   a   a   a
第一轮 l = 0
p       1   2   3   4   5   6   7   8       
sa[i]   1   2   3   4   5   6   7   8       1   1   1   1   1   1   1   1
第二轮 l = 1
p       8   1   2   3   4   5   6   7       
sa[i]   8   1   2   3   4   5   6   7       2   2   2   2   2   2   2   1
第三轮 l = 2
p       7   8   6   1   2   3   4   5 
sa[i]   8   7   6   1   2   3   4   5       3   3   3   3   3   3   2   1

以字符串"aabaaaab"为例

                                            1   2   3   4   5   6   7   8
        1   2   3   4   5   6   7   8       a   a   b   a   a   a   a   b
sa[i]   1   2   3   4   5   6   7   8       a   a   b   a   a   a   a   b
第一轮 l = 0
p       1   2   3   4   5   6   7   8       
sa[i]   1   2   4   5   6   7   3   8       1   1   2   1   1   1   1   2
第二轮 l = 1
p       8   1   3   4   5   6   2   7       
sa[i]   1   4   5   6   2   7   8   3       1   2   4   1   1   1   2   3
第三轮 l = 2
p       7   8   2   3   4   5   6   1  
sa[i]   4   5   6   1   7   2   8   3       4   6   8   1   2   3   5   7
.............

假设字符串的长度为n, 利用倍增法构造数组的代码如下：

int N = 1000007;
int sa[N+1] = {};
int rank[N+1] = {};
int tmp[N+1] = {};
bool equal(int a, int b, int l)
{
    return rank[a] == rank[b] && rank[a+l] == rank[b+l];
}
void doubleing(string s) {
    int n = s.length();
    int p[n+1] = {};
    for (int i = 1 ; i <= n; i++)
    {
        sa[i] = i;
        rank[i] = s[i-1];
    }
    int l = 0;
    int sig = 128;
    int pos = 0;
    while (pos < n) {    
        for (int i = n - l + 1; i <= n; i++) p[++pos] = i;
        for (int i = 1; i <= n; i++)
        {
            if (sa[i] > l) p[++pos] = sa[i] - l;
        }
        int cnt[sig+1] = {};
        for (int i = 1; i <= n; i++) cnt[rank[i]]++;
        for (int i = 1; i <= sig; i++) cnt[i] += cnt[i-1];
        for (int i = n; i; i--) sa[ cnt[ rank[p[i]] ] -- ] = p[i];
        pos = 0;
        for (int i = 1; i <= n; i++) tmp[sa[i]] = equal(sa[i], sa[i-1], l) ? pos : ++pos;
        // 上面这一行很重要，因为要用上一轮的rank所以不能直接用rank[SA[i]] = equal(....)
        for (int i = 1; i <= n; i++) rank[i] = tmp[i];
        sig = pos;
        l = !l? 1 : l<<1;
    }
}

得到rank[n+1] 翻译一下，假设字符串为"aabaaaab"

    1   2   3   4   5   6   7   8
    a   a   b   a   a   a   a   b
第一轮 
sa  1   2   4   5   6   7   3   8
    1   
    1   1
    1   1       1
    1   1       1   1
    1   1       1   1   1
    1   1       1   1   1   1
    1   1   2   1   1   1   1
    1   1   2   1   1   1   1   2
    

有几个难理解的地方在此记录下来：

1.为什么默认的sa[]是顺序的下标值？能不能乱填？
可以但不限于顺序的下标值。由于sa[]是从rank[]和p[]的得到的，而开始的p[]均为0，
所以可以为[4,2,3,1]这种乱序下标值，但是由于p[i]对应下标所以不能乱填，必须涵盖所有的下标。

2.为什么默认的rank[]是字符ascii码？
这个要从第一次循环来考虑，第一次循环l == 0,所以需要比较本身的大小，这时候就是按照ascii码比较的。

构造最长公共前缀
下面的i也都是从1开始
定义Height[i]为第i名和第i-1名的最长公共前缀，即后缀[sa[i]]和后缀[sa[i-1]]的最长公共前缀
定义H[i]为Height[rank[i]]
设suffix[k]为suffix[i-1]排序后的前一个，suffix[k]和suffix[i-1]的最长公共前缀为H[i-1],
若H[i-1] = 0或1 H[i] >= H[i-1]成立
若H[i-1] >= 2, 则H[i]和suffix[k+1]的最长公共前缀为H[i-1]-1且suffix[k+1]在H[i]的排序前面
若suffix[k+1]和H[i]之间的存在suffix[x],则suffix[x]和H[i]的公共前缀不可可能小于H[i-1]-1,(若小于，则不可能在两个之间)
根据这一点，可以得到如下代码求解最长公共前缀maxH

int maxH = -1;
int j = 0, k = 0;
for (int i = 1; i <= n; i++)
{
    for (k = k ? k-1: k, j = SA[rank[i]-1]; s[j+k] == s[i+k]; k++);//分号别忘了
    H[i] = k;
}

for (int i = 1; i <= n; i++)
{
    maxH = max(maxH, H[i]);
}