首页 > 代码库 > 字符串处理方法总结

字符串处理方法总结

自动机,KMP算法,Extend-KMP,后缀树,后缀数组,trie树,trie图及其应用

    涉及到字符串的问题,无外乎这样一些算法和数据结构:自动机,KMP算法,Extend-KMP,后缀树,后缀数组,trie树,trie图及其应用。 当然这些都是比较高级的数据结构和算法,而这里面最常用和最熟悉的大概是kmp,即使如此还是有相当一部分人也不理解kmp,更别说其他的了。当然一般的 字符串问题中,我们只要用简单的暴力算法就可以解决了,然后如果暴力效率太低,就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来, 这样的一些算法和数据结构实际上很少会被问到,不过如果使用它们一般可以得到很好的线性复杂度的算法。

    老实说,字符串问题的确挺复杂的,出来一个如果用暴力,hash搞不定,就很难再想其他的方法,当然有些可以用动态规划。下图主要说明下这些算法数据结构之间的关系。图中黄色部分主要写明了这些算法和数据结构的一些关键点。

    图中可以看到这样一些关系:extend-kmp 是kmp的扩展;ac自动机是kmp的多串形式;它是一个有限自动机;而trie图实际上是一个确定性有限自动机;ac自动机,trie图,后缀树实际上都是一种trie;后缀数组和后缀树都是与字符串的后缀集合有关的数据结构;trie图中的后缀指针和后缀树中的后缀链接这两个概念及其一致。

    后缀树的构造可以用Ukkonen算法在线性时间内完成[,但是不仅构造算法实现相当复杂,而且后缀树存在着致命弱点:空间开销大且对大字母表时间效率不理想。至于后缀数组下次阐述,这里简单介绍下extend-kmp。而在介绍extend-kmp之前,咱们先要回顾下KMP算法。

字符串处理方法总结