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

ecsmac
  • 304

AC 自动机简单来说就是:

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

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

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

回复
阅读 6k
3 个回答

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

看了BMKMP算法的代码, 简直太帅了!

广告: 字符串搜索算法BMKMPSUNDAYC实现

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

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

基于DFA的多正则引擎

  • AC 自动机解决了匹配多个精确 term 的问题;多正则引擎解决的是匹配多个正则表达式的问题。
  • 理想情况下 AC 自动机匹配过程中碰到 term 的结尾时触发动作:告诉调用者,在这里发现了完整匹配,能匹配的 term id 是 {id1,id2...} 。多正则引擎对正则表达式做同样的事情。
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏