Trie树
Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie有3个基本性质：
这是一个Trie结构的例子：
在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用10个字节（不包括指针占用的空间）。
后缀树
后缀树有点类似于Trie树，区别在于Trie树中的每个边只含有一个字符，而后缀树则是每个边包含若干字符。比如字符串XMADAMYX生成后缀树后就是下面的样子（$是为了避免，某个后缀是另外一个后缀的前缀的情况，比如X是XMADAMYX的前缀，如果不加以区分，很难在树中知道X也是一个合法的后缀）
后缀数组
http://www.cnblogs.com/cherish_yimi/archive/2009/10/12/1581666.html