类似 AC 自动机这样让人惊喜的算法还有哪些？

Question

AC 自动机简单来说就是：

1. 构建 Trie 树
2. 在 Trie 树上构建失配指针，成为 AC 自动机
3. 自动机上匹配字符串

学过了一年多从来不觉得有什么特别之处，直到今天才发现其简单直观的匹配方式和效率是有多赞！

所以想问一下大家还有其他类似让人惊叹不已的算法么？可以分享一下，互相学习。

Answer 1

AC自动机结合字符串搜索算法BM => ACBM算法

看了BM和KMP算法的代码, 简直太帅了!

广告: 字符串搜索算法BM和KMP和SUNDAYC实现

注: 算法的代码肯定不是我原创, 说实话, 看懂那段代码也是挺累的...

Answer 2

• 后缀数组, 后缀树， KMP
• AC自动机 实际上是 KMP 的升级版， 构建 fail 指针
• 经典的算法都是很巧妙的， 看看 算法导论 是个不错的选择. >.<

Answer 3

基于DFA的多正则引擎：

• AC 自动机解决了匹配多个精确 term 的问题；多正则引擎解决的是匹配多个正则表达式的问题。
• 理想情况下 AC 自动机匹配过程中碰到 term 的结尾时触发动作：告诉调用者，在这里发现了完整匹配，能匹配的 term id 是 {id1,id2...} 。多正则引擎对正则表达式做同样的事情。