数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后，你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起，跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法？
02 | 如何抓住重点，系统高效地学习数据结构与算法？
03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？
04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组：为什么很多编程语言中数组都从0开始编号？
06 | 链表（上）：如何实现LRU缓存淘汰算法?
07 | 链表（下）：如何轻松写出正确的链表代码？
08 | 栈：如何实现浏览器的前进和后退功能？
09 | 队列：队列在线程池等有限资源池中的应用
10 | 递归：如何用三行代码找到“最终推荐人”？
11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎？
12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？
13 | 线性排序：如何根据年龄给100万用户数据排序？
14 | 排序优化：如何实现一个通用的、高性能的排序函数？
15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能？
16 | 二分查找（下）：如何快速定位IP对应的省份地址？
17 | 跳表：为什么Redis一定要用跳表来实现有序集合？
18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？
19 | 散列表（中）：如何打造一个工业级水平的散列表？
20 | 散列表（下）：为什么散列表和链表经常会一起使用？
21 | 哈希算法（上）：如何防止数据库中的用户信息被脱库？
22 | 哈希算法（下）：哈希算法在分布式系统中有哪些应用？
23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？
24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？
25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？
26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树
27 | 递归树：如何借助树来求解递归算法的时间复杂度？
28 | 堆和堆排序：为什么说堆排序没有快速排序快？
29 | 堆的应用：如何快速获取到Top 10最热门的搜索关键词？
30 | 图的表示：如何存储微博、微信等社交网络中的好友关系？
31 | 深度和广度优先搜索：如何找出社交网络中的三度好友关系？
32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？
33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？
34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？
35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？
36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？
37 | 贪心算法：如何用贪心算法实现Huffman压缩编码？
38 | 分治算法：谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？
41 | 动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战：如何实现搜索引擎中的拼写纠错功能？
高级篇 (9讲)
43 | 拓扑排序：如何确定代码源文件的编译依赖关系？
44 | 最短路径：地图软件是如何计算出最优出行路径的？
45 | 位图：如何实现网页爬虫中的URL去重功能？
46 | 概率统计：如何利用朴素贝叶斯算法过滤垃圾短信？
47 | 向量空间：如何实现一个简单的音乐推荐系统？
48 | B+树：MySQL数据库索引是如何实现的？
49 | 搜索：如何用A*搜索算法实现游戏中的寻路功能？
50 | 索引：如何在海量数据中快速查找某个数据？
51 | 并行算法：如何利用并行处理提高算法的执行效率？
实战篇 (5讲)
52 | 算法实战（一）：剖析Redis常用数据类型对应的数据结构
53 | 算法实战（二）：剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战（四）：剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战（五）：如何用学过的数据结构和算法实现一个短网址系统？
加餐：不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争：羁绊前行的，不是肆虐的狂风，而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超：我是怎么学习《数据结构与算法之美》的？
总结课 | 在实际开发中，如何权衡选择使用哪种数据结构和算法？
《数据结构与算法之美》学习指导手册
加餐：春节7天练 (7讲)
春节7天练 | Day 1：数组和链表
春节7天练 | Day 2：栈、队列和递归
春节7天练 | Day 3：排序和二分查找
春节7天练 | Day 4：散列表和字符串
春节7天练 | Day 5：二叉树和堆
春节7天练 | Day 6：图
春节7天练 | Day 7：贪心、分治、回溯和动态规划
加餐：用户学习故事 (2讲)
用户故事 | Jerry银银：这一年我的脑海里只有算法
用户故事 | zixuan：站在思维的高处，才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里，终须一别
第2季回归 | 这一次，我们一起拿下设计模式！
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册
36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？
王争 2018-12-14
很多支持用户发表文本内容的网站，比如 BBS，大都会有敏感词过滤功能，用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。你有没有想过，这个功能是怎么实现的呢？
实际上，这些功能最基本的原理就是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容之后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“***”把它替代掉。
我们前面讲过好几种字符串匹配算法了，它们都可以处理这个问题。但是，对于访问量巨大的网站来说，比如淘宝，用户每天的评论数有几亿、甚至几十亿。这时候，我们对敏感词过滤系统的性能要求就要很高。毕竟，我们也不想，用户输入内容之后，要等几秒才能发送出去吧？我们也不想，为了这个功能耗费过多的机器吧？那如何才能实现一个高性能的敏感词过滤系统呢？这就要用到今天的多模式串匹配算法。
基于单模式串和 Trie 树实现的敏感词过滤
我们前面几节讲了好几种字符串匹配算法，有 BF 算法、RK 算法、BM 算法、KMP 算法，还有 Trie 树。前面四种算法都是单模式串匹配算法，只有 Trie 树是多模式串匹配算法。
我说过，单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》，如需阅读全部文章，
请订阅文章所属专栏。
请订阅文章所属专栏。
立即订阅
登录 后留言
精选留言(61)
zixuan思考题:
一、单模式串匹配：
1. BF： 简单场景，主串和模式串都不太长, O(m*n)
2. KP：字符集范围不要太大且模式串不要太长， 否则hash值可能冲突，O(n)
3. naive-BM：模式串最好不要太长（因为预处理较重），比如IDE编辑器里的查找场景； 预处理O(m*m), 匹配O(n)， 实现较复杂，需要较多额外空间.
4. KMP：适合所有场景，整体实现起来也比BM简单，O(n+m)，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快，原因不明.
5. 另外查资料的时候还看到一种比BM/KMP更快，且实现+理解起来都更容易的的Sunday算法，有兴趣的可以看这里:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
https://www.jianshu.com/p/2e6eb7386cd3
二、多模式串匹配：
1. naive-Trie: 适合多模式串公共前缀较多的匹配(O(n*k)) 或者 根据公共前缀进行查找(O(k))的场景，比如搜索框的自动补全提示.
2. AC自动机: 适合大量文本中多模式串的精确匹配查找, 可以到O(n).
2018-12-14 1 79
AF我只想说，老师你真牛X2018-12-14 38
bboy孙晨杰在看kmp和本节的ac自动机，很多文字描述我也理解不了，于是我就在纸上画一些具体的例子，然后按代码一步步的debug下去，虽然方法笨，但是很有助于理解。2018-12-19 1 19
O_o做安卓开发的，前边全部都理解+可动手手写。跟到最近几章感到面试可能确实用不到这些了，平时工作也确实用不到了。感谢老师最近的授课，通俗易懂！作者回复: 👍 厉害。最近这几讲不讲的话 知识就有缺陷 你可以不用太费劲看懂 知道有这个东西就行
2018-12-17 15- zixuan前面激动说错了哈 ，跟DATrie没有半毛钱关系，后者只是一种Trie的具体实现.
"其实，如果我们把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层"， 这里改成 "那么某个节点的失败指针只有可能指向比他所在层更小的层数的节点" 似乎更精确，虽然例子里刚好都是差一层，但实际应该可以往前跨多层的.
和KMP算法一样，这个通过层次遍历来编织failNode数组的过程非常精妙，真的就像是织网一样。2018-12-14 13 
润鑫红黑树、KPM跟AC自动机这几节有点跟不上。。2018-12-14 9
roc王争老师，想问一下，我前面的内容掌握了有80%，如果不是面试算法岗，应该还算过关吧？2018-12-14 1 8
blacknhole终于完全看懂了。
有几个疑问：
1，“首先 root 的失败指针为 NULL，也就是指向自己。”后半句是不准确或错误的，root的失败指针并非指向自身，因为root不等于null。
2，“如果 p 指向的节点有一个等于 b[i] 的子节点 x……”以及下文中提到的b[i]，是笔误吗？应该为a[i]吧，因为a才是主串。2018-12-23 2 6
TryTs老师，我觉得学你这个课之后除了学习新的知识之外，还能够让我能够了解平时间那些常见应用背后的操作，最关键的时候在激发我的好奇心，让我能够去思考那些技术。嗯……我觉得很多时候好奇心就是学好知识的基础2018-12-19 5
EidLeung老师，如果要添加模式串，怎么改fail指针啊？2018-12-14 4
coldparkfail数组的构建的作用我是这么理解的，请老师看看是不是对的：
1. 在已经匹配上的敏感词中找到是否还有子集包含敏感词
2.看这个子集的后续节点能否进一步匹配。
举个例子：
1. 敏感词是abc和bc，主串是abc，那么按照fail指针算法，abc中的c会链接到bc中的c，那么我匹配上了abc自然就相当于匹配上了bc，不用单独在主串中找是否含有bc。
2. 主串是abcd，敏感词是abc，bcd，如果我匹配上abc，但是发现abc后面没有d，然后发现abc的c链接到bcd中的c，转过去一看，果然后面有d，就不用单独在主串中找是否含有bcd了。2019-10-04 3
QQ怪正好要做这个敏感词过滤系统😂2019-03-05 3
深蓝...完犊子了 从字符串匹配开始就掉队了 之前红黑树也是一脸懵逼。2018-12-14 3 3
懒猫老师，这里求最长可匹配后缀子串没理解，您举的例子：abc的最长可匹配后缀子串为bc，但是按照kmp的思想，abc的前缀子串为a、ab，后缀子串为c、bc，这里bc就不是最长可匹配后缀子串了呀，而且abc的最长可匹配后缀子串长度应该为0，不是吗作者回复: 你理解错了。这里说的最长可匹配后缀子串是：其他模式串可以匹配到abc的最长后缀子串。并不是abc自己的后缀子串匹配自己。
2019-04-11 2
文祥之前没看代码，一直在想到底怎么一层一层的给失败指针赋值，想破头也想不到。这一手linkedlist用也太巧妙了吧，保证了一层一层，从左到右给失败指针赋值，感动的我都哭了。2019-03-20 2- QQ怪ac自动机跟DFA算法有啥不同?2019-03-05 2
Magic单模式串匹配算法：
1 BF算法实现简单，但性能较差，适合主串和模式串比较小的场景
2 RK算法对BF算法进行了改进，通过构造巧妙的哈希函数减少匹配的次数。适合主串和模式串较短，且字符集合范围较小的场景
3 BM算法对BF进行了改进，性能较高，适合大部分文本查询场景。但是其中的坏字符规则比较耗费内存，当内存比较紧张时，可以仅使用好后缀规则，或者使用KMP算法
4 KMP算法空间和时间复杂度都较优，在主串较长时，应该选用kmp算法
多模字符串匹配算法：
1 Trie树：空间换时间，当各个模式串之间具有公共前缀时，空间利用率较高，适合前缀匹配。对于精确匹配，其性能低于红黑树和哈希表
2 AC自动机：基于Trie树的多模式串匹配算法，在Trie树节点引入了失效指针，使得一次遍历即可求得所有匹配的模式串。非常适用于多模式串匹配的场景2019-10-02 1
森鱼字符串这几节真烧脑……作者回复: 那就看看https://mp.weixin.qq.com/s/t8z4KQMrTrR3NljtWJm2zg
2019-09-04 1
wahaha“我这里给出一个不是很紧确的上界。”
不是“紧确”应该是“精确”编辑回复: 没问题的 就是紧确 意思和精确类似 你可以查一查
2019-05-24 1
闫飞可以讲讲自动机的概念吧，否则总有些感觉突兀作者回复: 么机会了。专栏已经更新完了。不过，你的问题我记下来了，我会更新到我的公众号里，你可以关注我的公众号：“小争哥”
2019-01-17 1
收起评论