字符串匹配用到的数据结构总结: Trie, Suffix Tree/Array, KMP and DFA

Overview

字符串匹配用到的数据结构总结: 介绍Trie, Suffix Tree/Array, KMP and DFA的基本概念和注意点, 解释一些counter intuitive的知识点.

字符串匹配用到的数据结构总结: Trie, Suffix Tree/Array, KMP and DFA

这里只是介绍这些数据结构是什么, 理解what is it即可, 除非搞竞赛, 不然没太大必要一定要理解how to implement it, 做到能从概念上分析和使用就差不多了.

(1) 字典树(Trie): 其实可以理解成前缀树, 参考下面的链接, 大概知道这是个什么数据结构即可. 能够分析复杂度, 不要求现场实现.

good reference http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

注意 Trie是一个字典,也就是说他表示的是一组字符串和后缀树不一样, 后缀树只是一个字符串的模式

(2) 后缀树

对于基本概念看wiki: http://en.wikipedia.org/wiki/Suffix_tree  就够了 后缀树其实是一种特殊的trie, 暴力的朴素的理解就是把s的所有后缀都插入到一个trie里面就构成了对应这个string的一颗后缀树, 当然有线性方法可以构建, 但是概念上就这么理解就行了. 后缀树可以支持线性时间的exact string matching,  Longest common substring, longest palindromic  substring  (  利用LCP(longest common prefix), LCA(lowest common ancestor)   ) 等操作.

(3) 后缀数组

后缀树的缺点就是消耗存储空间太大, 那么后缀数组是一个折中的数据结构, 他相比后缀树提供的功能可能没那么多, 但是确实节省了很多空间. 具体wiki之即可

(4) 前缀函数

前缀函数是在(kmp)中出现的一个概念, 其实也就是一个数组, 但是利用前缀函数可以灵活应用, 比如求最短的循环节就是利用前缀函数

(5) 有限自动机

有限自动机是string matching比较复杂的一套系统化的匹配方法, 一般做理论可用, 实际做题的时候很少用.

未完待续: 这篇博文自己觉得写的还是比较乱, 有些概念自己心里是清楚的, 但是写的未必清楚, 权当作自己的备忘笔记吧。

Summary

字符串匹配用到的数据结构总结: 介绍Trie, Suffix Tree/Array, KMP and DFA的基本概念和注意点, 解释一些counter intuitive的知识点.

Written on May 27, 2013