本文改编自斯坦福大学CS 97SI: Introduction to Programming Contests的教学材料Suffix arrays – a programming contest approach

在算法竞赛中经常会遇到很多有关字符串子串的问题,或者是字符串后缀的问题,因此也就需要一种高效的数据结构及算法来处理这个问题。

什么是后缀数组?

为了更好地理解后缀数组,我们先来了解一种特殊的trie——后缀trie。一棵trie树是用来储存字符串的数据结构,其中每一个节点有和字母表大小一样多的孩子节点。本文的例子中只考虑小写字母,那么每个节点也就至多有26个孩子节点。每一条从父节点到孩子节点标注上一个字符,从根节点到叶子节点路径上标注的字符组合起来就是trie中保存着的一个字符串。显然地,在trie中查找一个字符串只需要时间复杂度(m是字符串长度),叟搜索时间和其中的字符串数量无关,这是一个实现字典的绝佳数据结构。

Continue reading