字符串：KMP Eentend-Kmp 自动机 trie图 trie树 后缀树 后缀数组   

2009-09-25 00:00:40|  分类： |  标签：  |字号 大中小 

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

老实说，我也一直觉得字符串问题挺复杂的，出来一个如果用暴力，hash搞不定，就很难再想其他的方法，当然有些可以用动态规划。不过为了解决这个老大难问题，还是仔细对这些算法和数据结构研读了一番。做个笔记，免得忘了还得重新思考老长时间。如果碰到字符串问题，也一般不会超过这些方法的范围了。先看一张图吧，主要说明下这些算法数据结构之间的关系。图中黄色部分主要写明了这些算法和数据结构的一些关键点。