后缀数组倍增算法注释详解

这个倍增算法看得我是真的难受。

其实我觉得这个算法是并不难的，他的倍增原理我最开始在知乎上看到的文章就看懂了。
主要是OI大佬精简的厉害，很多地方真的难以理解。还有基数排序上。

强烈强烈强烈强烈建议在学后缀数组之前先去学一学基数排序，就算没写，但必须看懂他。对基数排序了解越深，倍增算法越好理解。

附上倍增算法详细注释解剖

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 100010;
int sa[maxn];                      //SA数组，表示将S的n个后缀从小到大排序后把排好序的的后缀的开头位置顺次放入SA中
int t1[maxn], t2[maxn], buc[maxn]; //求SA数组需要的中间变量，不需要赋值
int rank[maxn], height[maxn];
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中

void buildSA(int s[], int n, int m)
{
    int p, *x = t1, *y = t2;
    //第一轮基数排序,对单个字符排序，如果s的最大值很大，此时无法用数组记录，可改为快速排序
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i; //排序内容是单个字符 从后向前，实现先出现的排前面
    for (int k = 1; k <= n; k <<= 1) {
        // 以下开始直接利用sa数组排序第二关键字
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;             // 后面的 k 个数第二关键字为空的最小
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k; // 这里的实现真的是非常简短巧妙。首先第二基数都是从j位开始的，小于 k 的就不需要考虑，因此我们将整个数组向前移动 k 个位置，并在最后 k 个位置补充 k 个最小元素，从而获得第二关键字的有序序列。
        // 这样数组y保存的就是按照第二关键字排序的结果
        //
        // 以下开始基数排序组合
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[y[i]]]++; //y数组并没有重复元素，这就意味着，只是将x数组的元素乱掉而已 那这又是为什么不直接换成 buc[x[i]]++ 已测试更改后无影响
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i]; // 反向，为了先出现的排前面，也就发挥了第二关键字的作用 ,若要先出现的排后面，则正向
        // 非常非常值得注意！！！！！！ 此时y 数组的顺序 就是组合的顺序 所有后面赋值的是 y[i]
        //
        // 以下开始根据sa和x数组计算新的x数组 , 重新申明 ！！ x 数组是 现有单个元素 第 i 位的位置
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        // 这里是上面那条的解释
        // 因为是有序的，所有重复元素只可能在旁边，如果出现重复元素则为 p-1，表示与上一条相等 否则 为 p++
        // 显然的，这里有离散化的作用
        if (p >= n) // 如果没有出现重复元素
            break;
        m = p; // 下次基数排序的最大值
    }
}

最后附上无注释模板，以备未来意外之需

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 100010;
int sa[maxn];
int t1[maxn], t2[maxn], buc[maxn]; 
int rank[maxn], height[maxn];

void buildSA(int s[], int n, int m)
{
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i; 
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;           
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[y[i]]]++; 
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i]; 
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n) 
            break;
        m = p; 
    }
}