什么是 后缀（Suffix）

S是一个长度为 N 的字符串，那么定义S的第 i 个后缀就是S的子串 S[i...n-1]

什么是 后缀数组（Suffix Array）

后缀数组作为一种数据结构，被广泛应用于数据压缩、生物信息学等领域。通俗地说后缀数组被应用于任何处理字符串与字符串匹配的场合。

后缀数组是各个排序后的后缀的起始位置组成的数组。

示例

当 S = abaab 时。

所有的后缀如下：

1
2
3
4
5
0. abaab
1. baab
2. aab
3. ab
4. b

依据字符串的比较对后缀进行排序后得到：

1
2
3
4
5
2. aab
3. ab
0. abaab
4. b
1. baab

因此字符串S的后缀数组为： (2, 3, 0, 4, 1)

后缀数组的构造

O(N2logN) 构造法

这是最朴素的构造方法效率，即获取所有后缀并使用O(NlogN)的排序算法如快排或者合并排序对这些后缀进行排序。而构造法的时间复杂度是O(N2logN)而不是O(NlogN)的原因是排序过程中两个后缀的比较复杂度为O(N)。下面我们将把比较的复杂度从O(N)降为O(logN)。

O(N log2 N) 构造法

比较的复杂度能够从O(N)降为O(logN)依赖于后缀的特性：这些后缀并不是随机的，而是同属于一个字符串的后缀，也就是说这些后缀有相同的公共部分可以供我们利用。

下面用示例说明。我们以所有后缀的首字母为基准排序，并对这些首字母赋予一个 rank 值代表他们之间的大小关系。

1
2
3
4
5
0. a|baab
0. a|ab
0. a|b
1. b|aab
1. b|

如上，以 | 左侧字符串为比较基准，字符串前的数字表示 | 左侧字符串对应的 rank。由此，rank(a) = 0， rank(b) = 1。

我们取两个字符进行比较时，比较分两步。首先比较第一个字符，如果相等则继续比较第二个字符。

1、对于 abaab 和 baab，因为二者首字母 rank 值已知且不同，因此 abaab 排序在 baab 之前。

2、对于 abaab 和 aab，因为而这首字母 rank 值已知且相同，因此继续看第二个字符，两者的第二个字符不同且 rank 值已知，所以 aab 排在 abaab 之前。

通过上面两个步骤的解析可以发现，在比较所有后缀的第一个字符之后，我们就已经获得了整个字符串 S 的所有字符的 rank 值。（因为所有后缀的首字符组在一起恰好为字符串S，联想后缀的定义即S从i(0 <= i < len(s))到S的最后一个字符所组成的字符串集合）

对于没有第二个字符的字符串我们认为它的第二部分 rank 值为最小值，这里设其为-1。例如 b 只有一个字符，因此它的前两个字符 rank 对就为（1， -1）

现在我们尝试以两个字符作为比较基准，有：

1
2
3
4
5
0. aa|b
1. ab|aab
1. ab|
2. b|
2. ba|ab

综上所述，对于字符串下次比较，我们选取4个字符，而4个字符的比较又可分为两部分：前两个字符和后两个字符。这又回到了上一步的过程。因此比较两个字符串时，我们只需比较前1、2、4、8、…、log(len(s))个字符。

下面是代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include "bits/stdc++.h"
using namespace std;
 
// suffixRank 保存每次遍历过程中每个字符串的Rank值 
// suffixRank[i][j] 代表第 i 次遍历，第 j 个后缀的 rank 
int suffixRank[20][int(1E6)];
// 示例： "abaab" 
// 对应的后缀数组： (2, 3, 0, 4, 1) 
// 创建一个保存每个后缀 rank 值序列的结构体。 
struct myTuple {  
    int originalIndex;   // 保存原始后缀首字母的序列号
    int firstHalf;       // 保存后缀前半部分的 rank 值
    int secondHalf;      // 保存后缀后半部分的 rank 值
};
// 后缀比较函数，时间复杂度O(1)
// 首先 a 的 firstHalf 是否与 b 的 firstHalf 相等
// 如果相等，则比较 secondHalf
// 否则比较结果取决于 firstHalf 的 rank 值大小
int cmp(myTuple a, myTuple b) {  
    if(a.firstHalf == b.firstHalf) return a.secondHalf < b.secondHalf;  
    else return a.firstHalf < b.firstHalf;  
}
int main() {
	
	// 输入字符串 S 
	// 保存 S 的长度到 N 中
    string s; cin >> s;
    int N = s.size();
	
	// 初始化 每个后缀的首字母 rank 值作为对应后缀的 rank 值 
	// 对于单字母 rank 值，以该子母与 a 差距作为 rank，因此 'a' = 0, 'b' = 1, 'c' = 2, ... ,'z' = 25
    for(int i = 0; i < N; ++i)
        suffixRank[0][i] = s[i] - 'a';
	// 创建每个后缀的 元组 数组
    myTuple L[N];
	
	// 遍历 log(n) 次，直到所有的后缀排序完毕
	// 'stp' 保存当前遍历次数
	// 'cnt' 保存将被比较的后缀长度 
	// 每次遍历， 我们用上一次遍历获得的值初始化每个后缀数组的元组
	
    for(int cnt = 1, stp = 1; cnt < N; cnt *= 2, ++stp) {
        for(int i = 0; i < N; ++i) {
            L[i].firstHalf = suffixRank[stp - 1][i];
            L[i].secondHalf = i + cnt < N ? suffixRank[stp - 1][i + cnt] : -1;
            L[i].originalIndex = i;
        }
		
		// 以 元组 为基准对 元组数组 排序
        sort(L, L + N, cmp);
		
		// 排序后，另排序最靠前的 rank 值初始化为0 
        // Initialize rank for rank 0 suffix after sorting to its original index
        // in suffixRank array
        suffixRank[stp][L[0].originalIndex] = 0;
        for(int i = 1, currRank = 0; i < N; ++i) {
			
			// 比较第 i 个后缀和第 i-1 个后缀
			// 如果二者相等，则将第 i-1 个后缀的 rank 值赋给第 i 个后缀
			// 否则第 i 个后缀的 rank 为第 i-1 个后缀的 rank 值加1 
            if(L[i - 1].firstHalf != L[i].firstHalf || L[i - 1].secondHalf != L[i].secondHalf)
                ++currRank;
            suffixRank[stp][L[i].originalIndex] = currRank;
        }
    }
    // 输出后缀数组 
    for(int i = 0; i < N; ++i) cout << L[i].originalIndex << endl;
    return 0;
}

后缀数组的应用

1、结合LCP（Longest Common Prefix）

2、模式匹配

3、 查找最长重复子串

4、 查找最长公共子串

5、 查找最长回文子串

参考文章

1、String Function Calculation Topics