Jinlong's Blog

笔记：后缀数组

发表于

介绍

假如要实现这样一个功能，给定一个字符串str，找出str中重复的最长的子串，比如，给定”banana”，其中最长的出现重复的子串为ana（分别出现在第1个位置和第3个位置上），穷解法的时间复杂度为O(m * n^2)，利用后缀数组可以在O(nlogn + n)的复杂度下实现此功能。
比如给定一个字符串”banana”，先列出其后缀：

1
2
3
4
5
6
banana
anana
nana
ana
na
a

然后对后缀进行排序

1
2
3
4
5
6
a
ana
anana
banana
na
nana

然后对排好序的后缀进行一次线性扫描即可找出”banana”中出现重复的最长的子串为”ana”，时间复杂度为O(nlogn + n)

实现

具体实现如下：

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
#include <iostream>
#include <cstring>
using namespace std;
//最大字符串长度
#define MAX_LENGTH 1024
//字符串比较函数
int cmp_char(const void *a, const void *b) {
	return strcmp(*((char**)a), *((char**)b));
}
//计算字符串a和字符串b的公共前缀长度
int compute_common_len(char *a, char *b) {
	int result = 0;
	while(*a != '\0' && *b != '\0' && *(a++) == *(b++))
		result++;
	return result;
}
int main() {
	char str[MAX_LENGTH];	//存储字符串
	char *pstr[MAX_LENGTH];	//后缀数组
	cout<<"input the string:";
	cin>>str;
	int i, limit = strlen(str);
	for(i = 0; i < limit; i++) {
		pstr[i] = &str[i];	//初始化后缀数组
	}
	qsort(pstr, limit, sizeof(char*), cmp_char);	//对后缀数组进行排序
	//输出排好序的后缀数组
	for(i = 0; i < limit; i++) {
		cout<<pstr[i]<<endl;
	}
	int max_len = -1;	//记录最大公共前缀长度
	int index = -1;		//记录结果在数组pstr中的索引
	int common_len;
	//线性扫描
	for(i = 1; i < limit; i++) {
		//计算pstr[i - 1]和pstr[i]的公共前缀长度
		common_len = compute_common_len(pstr[i - 1], pstr[i]);
		//如果计算出来的公共前缀长度比max_len大，则更新max_len和index
		if(common_len > max_len) {
			max_len = common_len;
			index = i - 1;
		}
	}
	//输出结果
	cout<<"result:"<<pstr[index]<<endl;
	return 0;
}

运行程序，输入banana，输出结果如下：

1
2
3
4
5
6
7
8
9
$ ./a.out
input the string:banana
a
ana
anana
banana
na
nana
result:ana

应用

稍微修改以上给出的代码，读取《鲁宾逊漂流记》里面的内容，然后找出小说中重复过的最长的一句话：

that if i did take this foolish step, god would not bless me, and i would have leisure hereafter to reflect upon having neglected his counsel

后缀数组还可用在文本编辑器的字符串搜索上，因为在文本编辑器中，可能需要频繁地进行搜索操作，所以每次搜索都使用KMP或者BM算法对文本就行遍历一遍那是不可行的，可以利用后缀数组建立后缀树（skiplist也可以），这样每次搜索的成本就降到了O(logn)，大大提升了性能。

参考

《编程珠玑》第十五章 珍珠字符串