2018-12-14思考题:
一、单模式串匹配：
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).
展开 2 86
2018-12-14我只想说，老师你真牛X 43
2018-12-19在看kmp和本节的ac自动机，很多文字描述我也理解不了，于是我就在纸上画一些具体的例子，然后按代码一步步的debug下去，虽然方法笨，但是很有助于理解。 1 22
2018-12-17做安卓开发的，前边全部都理解+可动手手写。跟到最近几章感到面试可能确实用不到这些了，平时工作也确实用不到了。感谢老师最近的授课，通俗易懂！作者回复: 👍 厉害。最近这几讲不讲的话 知识就有缺陷 你可以不用太费劲看懂 知道有这个东西就行
1 21- 2018-12-14前面激动说错了哈 ，跟DATrie没有半毛钱关系，后者只是一种Trie的具体实现.
"其实，如果我们把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层"， 这里改成 "那么某个节点的失败指针只有可能指向比他所在层更小的层数的节点" 似乎更精确，虽然例子里刚好都是差一层，但实际应该可以往前跨多层的.
和KMP算法一样，这个通过层次遍历来编织failNode数组的过程非常精妙，真的就像是织网一样。 16 
2018-12-14红黑树、KPM跟AC自动机这几节有点跟不上。。 15
2018-12-14王争老师，想问一下，我前面的内容掌握了有80%，如果不是面试算法岗，应该还算过关吧？ 3 12
2018-12-23终于完全看懂了。
有几个疑问：
1，“首先 root 的失败指针为 NULL，也就是指向自己。”后半句是不准确或错误的，root的失败指针并非指向自身，因为root不等于null。
2，“如果 p 指向的节点有一个等于 b[i] 的子节点 x……”以及下文中提到的b[i]，是笔误吗？应该为a[i]吧，因为a才是主串。 3 7
2018-12-19老师，我觉得学你这个课之后除了学习新的知识之外，还能够让我能够了解平时间那些常见应用背后的操作，最关键的时候在激发我的好奇心，让我能够去思考那些技术。嗯……我觉得很多时候好奇心就是学好知识的基础 5
2018-12-14老师，如果要添加模式串，怎么改fail指针啊？ 4
2018-12-14完犊子了 从字符串匹配开始就掉队了 之前红黑树也是一脸懵逼。 7 4
2019-10-04fail数组的构建的作用我是这么理解的，请老师看看是不是对的：
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了。展开 3
2019-03-05正好要做这个敏感词过滤系统😂 3
2019-04-11老师，这里求最长可匹配后缀子串没理解，您举的例子：abc的最长可匹配后缀子串为bc，但是按照kmp的思想，abc的前缀子串为a、ab，后缀子串为c、bc，这里bc就不是最长可匹配后缀子串了呀，而且abc的最长可匹配后缀子串长度应该为0，不是吗作者回复: 你理解错了。这里说的最长可匹配后缀子串是：其他模式串可以匹配到abc的最长后缀子串。并不是abc自己的后缀子串匹配自己。
2
2019-03-20之前没看代码，一直在想到底怎么一层一层的给失败指针赋值，想破头也想不到。这一手linkedlist用也太巧妙了吧，保证了一层一层，从左到右给失败指针赋值，感动的我都哭了。 2- 2019-03-05ac自动机跟DFA算法有啥不同? 2
2018-12-14请教下老师，第三幅图，如果把d换成e，那pc的失败指针是不是要指向root了，但是和之前说的只会指向上一层节点不一样啊，希望老师解答下作者回复: 不是指向上一层 而是上层 上几层都有哦可能
2
2020-01-13贴一个感觉不错的视频，可以结合着来看。https://www.bilibili.com/video/av81263689?p=1 1 1
2019-10-02单模式串匹配算法：
1 BF算法实现简单，但性能较差，适合主串和模式串比较小的场景
2 RK算法对BF算法进行了改进，通过构造巧妙的哈希函数减少匹配的次数。适合主串和模式串较短，且字符集合范围较小的场景
3 BM算法对BF进行了改进，性能较高，适合大部分文本查询场景。但是其中的坏字符规则比较耗费内存，当内存比较紧张时，可以仅使用好后缀规则，或者使用KMP算法
4 KMP算法空间和时间复杂度都较优，在主串较长时，应该选用kmp算法
多模字符串匹配算法：
1 Trie树：空间换时间，当各个模式串之间具有公共前缀时，空间利用率较高，适合前缀匹配。对于精确匹配，其性能低于红黑树和哈希表
2 AC自动机：基于Trie树的多模式串匹配算法，在Trie树节点引入了失效指针，使得一次遍历即可求得所有匹配的模式串。非常适用于多模式串匹配的场景展开 1
2019-09-20https://www.cnblogs.com/sclbgw7/p/9260756.html，这篇文章跟老师写的文章互相补充着看，ac自动机的概念就一目了然了 1 1