有限自动机A用来识别字符串，它由5部分组成：
1）alphabet，字符集
2）states，状态集合
3）init，初始状态
4）trans(s, ch)，状态转移函数
5）end 可接受state 集合
A(str) == true的意思是，A可以接受字符串str，即从初始状态init读入str所有字符之后所达到的状态属于集合end， tran(init, str) 属于 end
一个有限自动机对应一个可接受的字符串集合。
一个Trie就是一个自动机，可识别词典里的词
后缀Trie 可以识别一个text的所有后缀，如果让每个结点都是可接受状态，则可以识别text的所有子串，而且复杂度仅仅是O(m)，m为pattern的长度。后缀Trie的问题是构造它需要O(n^2)的时间和空间复杂度。Suffix Tree本质上和后缀Trie一样，是后缀Trie的一种高效实现，使得时间和空间复杂度都是O(n)。
这是搜索的角度，即text是固定的，pattern(关键字，keyword）是变化的。kmp、AC自动机、RE则是是另一个角度，固定的是pattern，变化的是text。
查询关键字一般情况是一个短语"Hanzhou opens G20 submit"
exact match：普通Trie，只有短语结尾才是可接受状态
prefix match：普通Trie，每个结点都标记为可接受状态
suffix match：suffix Trie，只有短语结尾是可接受状态
substring match：suffix Trie，每个结点都标记为可接受状态
1) suffix trie不一定是真的把 每个suffix都插入，比如 "Hanzhou opens G20 submit", 可以只把从4个词Hanzhou，Opens，G20， Submit开始的4个后缀插入，这样可以避免无意义的词。
2) 所谓每个结点都标记为可接受状态：也不一定是真的每个结点，可以排除空格，甚至只是每个词的结尾才标记
