后缀数组

OI 笔记 算法 字符串

目录：

后缀排序

前言

前前后后折腾了好几天才明白过来后缀排序，写个博客记录一下。[1]

后缀排序真的没啥好介绍的了……
就是一个裸的后缀数组…… ——zcy

当时看到zcy巨佬的这句话很是崩溃，所以，我现在学会后缀排序后，给大家详细地介绍一下后缀排序的基础知识。

概述

首先考虑朴素的暴力排序，由于快排会进行$O(n\log n)$次比较，而字符串比较又是$O(n)$的，所以总时间复杂度为$O(n^2\log n)$，可以处理$n\le10^4$的情形，不大好。要是这样就行我还学这么长时间干什么

下面祭出伟大的倍增算法：

倍增算法的大体思路是这样的:

由于后缀间存在包含关系，所以后缀比较次数可以减少，比如说起点位置为1的后缀（以后将起点位置为x的后缀简称为后缀x）的第2个字符就是后缀2的第1个字符，而后缀1和后缀2的第2个字符的关系其实就是后缀2和后缀3的第1个字符的关系。这样，我们就可以减少一部分比较。同时，运用倍增的思想，我们不是逐个字符比较，而是倍增地增加比较长度，同时尽可能的使用已经算过的数据。

上面这段话还是太抽象了，我们结合代码分析，这里我们以字符串aababaa为例。

数据结构

以下是代码中会用到的变量&数组

char s[N]; // 原始字符串 
int a[N]; // 字符转数字且后移一位，方便处理
int sa[N]; // 排名为i的后缀的编号 
int rak[N]; // 后缀i的排名 
int tmp[N]; // 基数排序第二关键字
int tax[N]; // 基数排序数组
int len; // 字符串长度 
int m; // 基数排序关键字范围 

这些数组的意义都不是很明朗，先搞明白sa和rak关系就行

sa[ rak[i] ] = i;
rak[ sa[i] ] = i;

请对照中文仔细理解这两行的意义，这关乎到是否能看懂接下来的内容

主要过程

首先先对每个后缀首字母排序。这里我们不使用快排，而是用基数排序，现在先不用管啥是基数排序，只要知道:

• 复杂度$O(nm)$，其中m为关键字个数（在这里是2）
• 与桶排类似（其实后缀排序也能用桶排）
• 简称鸡排基排

for (int i = 1; i <= len; ++i) {
    rak[i] = a[i];
    tmp[i] = i; 
} 
m = 127;
Rsort(); 

我们将各个后缀按后缀的首字母进行排序，即用一个二元组$(S[i],i)$表示后缀i（这里的第二关键字意义是为了让各个后缀不相同，在基排时不出错，其实如果是不同的随机数也可以）。

这里第5,6行是基排的内容，稍后细细的讲。

接下来就是倍增的排序的过程。

for (int w = 1; p < len; w <<= 1) {
// do something...
} 

为了方便叙述，我们将一个字符串（后缀）分为3部分，第1部分和第2部分长度均为上文的w，第3部分是剩下的部分。

排序时第1关键字是第1部分，第2关键字是第2部分。

p = 0;  
for (int i = 1; i <= w; ++i) tmp[++p] = len - w + i; 
for (int i = 1; i <= len; ++i) if (sa[i] > w) 
    tmp[++p] = sa[i] - w; 
Rsort();

这段代码的前6行都是对第2部分排序，第3行中的tmp[++p] = len - w + i意思是后缀$len-w+i$排在最前面（因为它长度小于w，没有第二部分），第6行较难理解：考虑一个后缀，如果其排名为p，那么，这个后缀向前推移w个字符的后缀的第2关键字排名就为p。（不考虑长度小于w的后缀）（可以先停下来想一想）
然后就是喜闻乐见的基排了（基排能处理出sa数组）。

接下来要用sa和之前的rak更新rak，这是tmp已经没用了，所以：

swap(rak, tmp); 

或者也可以写memcpy(tmp, rak, sizeof tmp)。
然后：

rak[sa[1]] = 1;
p = 1; // 现在用到的排名 
for (int i = 2; i <= len; ++i) {
    rak[sa[i]] = 
        ( tmp[ sa[i-1] ] == tmp[ sa[i] ] 
        && tmp[ sa[i-1]+w ] == tmp[ sa[i]+w ] ) ?
        p : ++p;
}

第1行很好理解，第2,3行也还可以，第4,5,6,7行%@!!#!$...看不懂啊！！！
不着急，我们慢慢分析，第4行指出我们要处理的是 排序后排名为i的后缀 只看1,2部分的排名（因为剩下的部分并没有参与排序，这个序是不准的）。第5,6行是说如果这个后缀和“排名”为i-1的后缀第1部分一样（5）且第2部分也一样（6）（别忘了现在的tmp是原来的rak），那么（第7行）排名不变，否则排名+1。

最后，更新基排范围m = p。

终于讲完主要过程了，没有理解的可以先再看看前面的内容。

基数排序

下面开始讲基排。

先上代码吧：

for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= len; ++i) ++tax[rak[i]];
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = len; i >= 1; --i) sa[ tax[ rak[ tmp[i] ] ]-- ] = tmp[i];

第1行清空，第2行类似桶排，第3行求前缀和，这样就可以快速的求出某个rak的排名，第4行%@!!#!$又是TMD什么玩意！
回顾这几个数组的定义，我们可以翻译这句话：

第2关键字排名为i的后缀的排名是这个后缀第一关键字排名

这显然是有问题的，然而我们倒序枚举就保证了正确性。

完整代码

char s[N]; // 原始字符串 
int a[N];
int sa[N]; // 排名为i的后缀起点的位置 
int rak[N]; // 基数排序第一关键字,起点为i的后缀的排名
int tmp[N]; // 基数排序第二关键字 or 临时数组
int tax[N]; // 基数排序数组
int len; // 字符串长度 
int m; // 基数排序关键字范围 
inline void Ssort() {
    // 确定初始序 
    for (int i = 1; i <= len; ++i) {
        rak[i] = a[i]; // 初始时后缀排名为首字母序 所以第一关键字是a[i] 
        tmp[i] = i; // 第二关键字使后缀维持原序 
    } 
    m = 127; // 设定关键字范围为char范围 
    Rsort(); // 排序 
    // 倍增法后缀排序
    int p = 0; 
    for (int w = 1; p < len; w <<= 1) { // w是每个关键字的长度 
        p = 0; // 辅助下标 
        // 长度不足w的后缀排名最靠前 
        for (int i = 1; i <= w; ++i) tmp[++p] = len - w + i; 
        for (int i = 1; i <= len; ++i) if (sa[i] > w) // 对于长度大于w的后缀 
            tmp[++p] = sa[i] - w; 
        Rsort();
        swap(rak, tmp); 
        rak[sa[1]] = 1;
        p = 1; // 现在用到的排名 
        for (int i = 2; i <= len; ++i) {
            rak[sa[i]] = 
                ( tmp[ sa[i-1] ] == tmp[ sa[i] ] 
                && tmp[ sa[i-1]+w ] == tmp[ sa[i]+w ] ) ?
                p : ++p;
        }
        m = p; // 更新排序范围 
    } 
}
inline void Rsort() {
    for (int i = 1; i <= m; ++i) tax[i] = 0;
    for (int i = 1; i <= len; ++i) ++tax[rak[i]];
    for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
    for (int i = len; i >= 1; --i) sa[ tax[ rak[ tmp[i] ] ]-- ] = tmp[i];
} 
int main() {
    scanf("%s", s);
    len = strlen(s);
    for (int i = 0; i <= len; ++i) a[i+1] = s[i];
    Ssort();
    for (int i = 1; i <= len; ++i) printf("%d ", sa[i]);
    return 0;
}