IOI2009 国家集训队论文 后缀数组 罗穗骞
信息学奥林匹克
China Nation Olympiad in Informatics
国家集训队论文
题
题
题
题 目：
目：
目：
目： 后缀数组 —— 处理字符串的有力工具
作
作
作
作 者：
者：
者：
者： 罗穗骞
指导教师：
指导教师：
指导教师：
指导教师： 张学东
学
学
学
学 校：
校：
校：
校： 华南师范大学附属中学
完成时间：
完成时间：
完成时间：
完成时间： ２００９年１月
IOI2009 国家集训队论文 后缀数组 罗穗骞
2
目录
摘要 ………………………………………………………………………………… 4
关键字 ……………………………………………………………………………… 4
正文 ………………………………………………………………………………… 4
一、 后缀数组的实现 ………………………………………………………………… 4
1 ． 1 基本定义 ………………………………………………………………… 4
1 ． 2 倍增算法 ………………………………………………………………… 6
1 ． 3 DC3 算法 ………………………………………………………………… 9
1
．
4 倍增算法与 DC3 算法的比较 …………………………………………… 1 4
二、后缀数组的应用 ……………………………………………………………… 15
2
．
1 最长公共前缀 …………………………………………………………… 1 5
例 1 ： 最长公共前缀 …………………………………………………… 1 7
2
．
2 单个字符串的相关问题 ………………………………………………… 1 7
2
．
2
．
1 重复子串 ……………………………………………………… 1 8
例 2 ： 可重叠最长重复子串 ……………………………………… 1 8
例 3
： 不可重叠最长重复子串 （
pku1743
）
……………………… … 18
例 4
： 可重叠的最长重复子串 （
pku3261
）
……………………… … 19
2
．
2
．
2 子串的个数 …………………………………………………… 1 9
例 5 ：不相同的子串的个数（ spoj694,spoj705 ） ……………… 1 9
2
．
2
．
3 回文子串 ……………………………………………………… 1 9
例 6
： 最长回文子串 （
ural1297
）
………………………………… 20
2
．
2
．
4 连续重复子串 ………………………………………………… 2 0
例 7 ： 连续重复子串 (pku2406) …………………………………… 2 0
例 8 ： 重复次数最多的连续重复子串 (spoj687,pku3693) ……… 2 1
2
．
3 两个字符串的相关问题 ………………………………………………… 2 1
2
．
3
．
1 公共子串 ……………………………………………………… 2 2
例 9 ： 最长公共子串 (pku2774,ural1517) ……………………… 2 2
2
．
3
．
2 子串的个数 …………………………………………………… 2 3
IOI2009 国家集训队论文 后缀数组 罗穗骞
3
例 10 ： 长度不小于 k 的公共子串的个数 (pku3415) …………… 2 3
2
．
4 多个字符串的相关问题 ………………………………………………… 2 3
例 11
： 不小于
k 个字符串中的最长子串 (pku3294) …………………… 24
例 12 ： 每个字符串至少出现两次且不重叠的最长子串 (spoj220) …… 2 4
例 13 ： 出现或反转后出现在每个字符串中的最长子串 (pku3294) …… 2 4
三、结束语 ………………………………………………………………………… 25
参考文献 …………………………………………………………………………… 25
致谢 ………………………………………………………………………………… 25
IOI2009 国家集训队论文 后缀数组 罗穗骞
4
后
后
后
后 缀
缀
缀
缀 数
数
数
数 组
组
组
组
----
----
----
---- 处理字符串的有力工具
处理字符串的有力工具
处理字符串的有力工具
处理字符串的有力工具
【
【
【
【 摘要
摘要
摘要
摘要 】
】
】
】
后缀数组是处理字符串的有力工具。 后缀数组是后缀树的一个非常精巧 的
替代品， 它比后缀树容易编程实现， 能够实现后缀树的很多功能而时间复杂度 也
并不逊色，而且它比后缀树所占用的内存空间小很多。 可以说，在信息学竞赛 中
后缀数组比后缀树要更为实用。 本文分两部分。 第一部分介绍两种构造后缀数 组
的方法，重点介绍如何用简洁高效的代码实现， 并对两种算法进行了比较。第 二
部分介绍后缀数组在各种类型题目中的具体应用。
【
【
【
【 关键字
关键字
关键字
关键字 】
】
】
】
字符串 后缀 后缀数组 名次数组 基数排序
【
【
【
【 正文
正文
正文
正文 】
】
】
】
一、后缀数组的实现
一、后缀数组的实现
一、后缀数组的实现
一、后缀数组的实现
本节主要介绍后缀数组的两种实现方法： 倍增算法和 DC3 算法 ， 并对两种 算
法进行了比较。 可能有的读者会认为这两种算法难以理解， 即使理解了也难以 用
程序实现。本节针对这个问题， 在介绍这两种算法的基础上，还给出了简洁高 效
的代码。其中倍增算法只有 25 行， DC3 算法只有 40 行。
１．１
１．１
１．１
１．１ 基本定义
基本定义
基本定义
基本定义
子串： 字符串 S 的子串 r[i..j] ， i ≤ j ，表示 r 串中从 i 到 j
这一段，
也就是顺次排列 r[i],r[i+1],...,r[j] 形成的字符串。
后缀： 后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字
IOI2009 国家集训队论文 后缀数组 罗穗骞
5
符串 r 的从 第 i 个字符开始的后缀表示为 Suffix(i) ，也就是
Suffix(i)=r[i..len(r)] 。
大小比较： 关于字符串的大小比较，是指通常所说的 “ 字典顺序
”
比较， 也
就是对于两个字符串 u 、 v ，令 i 从 1 开始顺次比较 u[i] 和 v[i] ，如果
u[i]=v[i] 则令 i 加 1 ，否则若 u[i]<v[i] 则认为 u<v ， u[i]>v[i] 则认为 u>v
（也就是 v<u
） ，比较结束。如果
i>len(u) 或者 i>len(v) 仍比较不出结果，那
么若 len(u)<len(v) 则认为 u<v ，若 len(u)=len(v) 则认为 u=v ，若
len(u)>len(v) 则 u>v 。
从字符串的大小比较的定义来看， S 的两个开头位置不同的后缀 u 和 v 进
行比较的结果不可能是相等，因为 u=v 的必要条件 len(u)=len(v) 在这里不可
能满足。
后缀数组：
后缀数组 SA 是一个一维数组， 它保存 1..n 的某个排列 SA[1 ]
，
SA[2] ， …… ， SA[n] ，并且保证 Suffix(SA[i]) < Suffix(SA[i+1]) ， 1 ≤ i<n
。
也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺
次放入 SA 中。
名次数组： 名次数组 Rank[i] 保存的是 Suffix(i) 在所有后缀中从小到大 排
列的 “ 名次
”
。
简单的说，后缀数组是 “ 排第几的是谁？
”
，名次数组是 “ 你排第几？
”
。
容
易看出，后缀数组和名次数组为互逆运算。如图 1 所示。
- 1
- 2
- 3
- 4
- 5
- 6
前往页