Trie and Suffix
前缀树(trie)和后缀树(suffix)是两种非常重要的数据结构，往往用来加速字符串的匹配和查找。具体的介绍可见下面的资料：
http://blog.csdn.net/luowen3405/archive/2011/04/01/6295839.aspx
http://blog.csdn.net/TsengYuen/archive/2009/11/16/4815921.aspx
Trie和Suffix最大的不同是，Trie是面向一个字符串的集合，而Suffix是面向一个字符串
在面试题目中，一些经典的前缀和后缀应用如下：
Suffix Tree:
求两个字符串的最长公共子串。
1. The longest common substring of two strings, txt1 and txt2, can be found by building a generalized suffix tree for txt1 and txt2: Each node is marked to indicate if it represents a suffix of txt1 or txt2 or both. The
deepest node marked for both txt1 and txt2 represents the longest common substring.
2. Equivalently, one can build a (basic) suffix tree for the string txt1$txt2#, where `$' is a special terminator for txt1 and `#' is a special terminator for txt2. The longest common substring is indicated by the deepest fork node that has both `...$...' and `...#...' (no $) beneath it.
求一个字符串的最长重复子串
Add a special end of string character, e.g. `$', to txt and build a suffix tree; the longest repeated substring of txt is indicated by the deepest fork node in the suffix tree, where depth is measured by the number of characters traversed from the root, i.e., `issi' in the case of `mississippi'. The longest repeated substring can be found in O(n) time using a suffix tree.
求一个字符串的最长回文
A palindrome is a string, P, such that P=reverse(P). e.g. `abba'=reverse(`abba'). e.g. `ississi' is the longest palindrome in `mississippi'. The longest palindrome of txt can be found in O(n) time, e.g. by building the suffix tree for txt$reverse(txt)# or by building the generalized suffix tree for txt and reverse(txt).
Trie
字典
A common application of a trie is storing a dictionary, such as one found on a mobile telephone. Such applications take advantage of a trie's ability to quickly search for, insert, and delete entries; however, if
storing dictionary words is all that is required (i.e. storage of information auxiliary to each word is not required), a minimal acyclic deterministic finite automaton would use less space than a trie.
页:
[1]