sin(x)

Tag: 字符串

算法笔记:后缀自动机

本文改编自MAXimal :: algo :: Суффиксный автомат. Построение и применения的Google机翻版(什么玩意儿)

后缀自动机是一个处理字符串相关问题很有用的工具,例如检查一个字符串在另外一个字符串中是否出现过,计算一个字符串中不同子串的数量——它们都可以在线性时间内被解决。

从直观上看,后缀自动机保存着所有子串的信息,对于长度为n的字符串来说,它的后缀自动机只需要的空间,同时构造它的时间复杂度为

Continue reading

算法笔记:后缀数组

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

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

什么是后缀数组?

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

Continue reading