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

Question

AC自动机简单来说就是：
构建Trie树
在Trie树上构建失配指针，成为AC自动机
自动机上匹配字符串
学过了一年多从来不觉得有什么特别之处，直到今天才发现其简单直观的匹配方式和效率是有多赞！
所以想问一下大家还有其他类似让人惊叹不已的算法么？可以分享一下，互相学习。

Answer 1

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