36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？
该思维导图由 AI 生成，仅供参考
基于单模式串和 Trie 树实现的敏感词过滤
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
AC自动机是一种多模式串匹配算法，通过构建Trie树实现了高效的敏感词过滤功能。相比传统的单模式串匹配算法，AC自动机能够一次性查找多个模式串的匹配，从而提高了匹配效率。文章介绍了AC自动机的原理和应用，指出了其在敏感词过滤系统中的重要性。通过对敏感词字典进行预处理，构建Trie树结构，可以实现高效的敏感词过滤功能。此外，文章还提到了AC自动机算法的优化改进方法，进一步提高了Trie树的效率。AC自动机的构建过程包括构建Trie树和构建失败指针，匹配过程中利用失败指针实现高效的模式串匹配。文章还分析了AC自动机在敏感词过滤中的时间复杂度，指出其性能非常高，尤其在大规模敏感词匹配时表现突出。总的来说，AC自动机是一种高效的多模式串匹配算法，特别适用于敏感词过滤系统，能够显著提高系统性能。
《数据结构与算法之美》，新⼈⾸单¥68
全部留言(116)
- 最新
- 精选
O_o做安卓开发的，前边全部都理解+可动手手写。跟到最近几章感到面试可能确实用不到这些了，平时工作也确实用不到了。感谢老师最近的授课，通俗易懂！作者回复: 👍 厉害。最近这几讲不讲的话 知识就有缺陷 你可以不用太费劲看懂 知道有这个东西就行
2018-12-17453
闫飞可以讲讲自动机的概念吧，否则总有些感觉突兀作者回复: 么机会了。专栏已经更新完了。不过，你的问题我记下来了，我会更新到我的公众号里，你可以关注我的公众号：“小争哥”
2019-01-179
懒猫老师，这里求最长可匹配后缀子串没理解，您举的例子：abc的最长可匹配后缀子串为bc，但是按照kmp的思想，abc的前缀子串为a、ab，后缀子串为c、bc，这里bc就不是最长可匹配后缀子串了呀，而且abc的最长可匹配后缀子串长度应该为0，不是吗作者回复: 你理解错了。这里说的最长可匹配后缀子串是：其他模式串可以匹配到abc的最长后缀子串。并不是abc自己的后缀子串匹配自己。
2019-04-1126
森鱼字符串这几节真烧脑……作者回复: 那就看看https://mp.weixin.qq.com/s/t8z4KQMrTrR3NljtWJm2zg
2019-09-0425
wahaha“我这里给出一个不是很紧确的上界。” 不是“紧确”应该是“精确”编辑回复: 没问题的 就是紧确 意思和精确类似 你可以查一查
2019-05-243
吴宇晨请教下老师，第三幅图，如果把d换成e，那pc的失败指针是不是要指向root了，但是和之前说的只会指向上一层节点不一样啊，希望老师解答下作者回复: 不是指向上一层 而是上层 上几层都有哦可能
2018-12-143
djfhchdhif (p == null) p = root; // 这里能否在p = root之后就直接continue？？作者回复: 👍可以加，不加逻辑也没错
2019-05-23
自信来自成功的体验老师您好！ 如果ac算法里面有好多需要跳转的 是每个都会跳转吗？ 比如 she her hee hea 会怎么实现作者回复: ac自动机的跳转是通过fail指针来实现的
2019-03-04
一修💤在工作中遇到过这个问题 当时我是把敏感词表甚至一些正则的pattern组合在一起用或相连，编译成一个大的pattern对象，然后对字符串进行验证。效率似乎也不低哎 不知道和这个AC自动机的差距在哪里作者回复: 正则表达式是基于回溯搜索。效率这个东西要在大规模数据的情况下才能比较出来。
2019-01-21- 樱桃子77想请教一点：即便没有AC自动机，单纯Trie，也可以多模式匹配吧？就像你文章开始说的那样，无论匹配成不成功，下一个主串里的词从新开始，而指向Trie的指针也重新指向root. 这样可以吗？ 多谢。
作者回复: 可以的
2018-12-20
