【读书笔记】数据结构与算法之美 第8章 字符串匹配算法
《数据结构与算法之美》，王争 著
标签：数据结构、算法
第8章 字符串匹配算法
一、BF算法（暴力匹配算法）
这一部分介绍了
BF算法的原理和实现
BF算法的性能分析
编程语言中的查找、替换函数是怎样实现的
笔记：很多实际应用中，模式串和主串的长度都不会太长，BF算法本身代码编程非常简单，不容易出bug，再加上在匹配过程中，出现失配即可提前终止算法，所以在实际的软件开发中，绝大部分情况下，BF算法就够用了；
常用的编程语言中提供的字符串查找函数采用的算法就是BF算法（时间复杂度最坏是O(nm)）。如果字符串匹配是软件的核心功能或性能瓶颈时，开发人员就不能使用编程语言提供的现成函数了（因为一般都是BF算法），而是要依据数据特点、性能要求、选择合适的字符串匹配算法从零开始编程实现。
另外，字符串匹配算法的性能分析需要涉及两个变量：主串和模式串的长度，这也是要注意的。
二、RK算法（Rabin-Karp算法）
这一部分介绍了
RK算法的原理与实现
RK算法的性能分析
笔记：RK算法是借助哈希算法对BF算法进行改造，时间复杂度为O(n)。
三、BM算法（Boyer-Moore算法）
这一部分介绍了
BM算法的核心思想
BM算法的原理分析
BM算法的代码实现（书中篇幅较长）
BM算法的性能分析
笔记：BM算法原理复杂，理解困难，但它是一种非常高效的字符串匹配算法，时间复杂度比RK算法低，在实际的软件开发中应用比较多。
四、KMP算法（Knuth-Morris-Pratt算法）
这一部分介绍了
KMP算法的基本原理
失效函数的计算方法
KMP算法的性能分析
笔记：KMP算法的时间复杂度O(m+n)。KMP算法借鉴了BM算法的思想。学习KMP算法最复杂的是next数组的计算。
五、Trie树
这一部分介绍了
Trie树的定义
Trie树的代码实现
Trie树的性能分析
Trie树与哈希表、红黑树的比较
Trie树的应用：搜索引擎的搜索关键词提示功能
笔记：Trie树是一种非常高效的字符串匹配算法，借助空间换时间的思路。特别适合查找前缀匹配的字符串。
六、AC自动机
这一部分介绍了
基于单模式串的敏感词过滤
基于Trie树的敏感词过滤
基于AC自动机的敏感词过滤
AC自动机的性能分析
笔记：AC自动机是基于Trie树的一种改进结构，也借鉴了KMP算法中的next数组的思想。多模式匹配算法是为了快速地在主串中查找多个模式串，适合模式串集合不频繁更新的场景，如敏感词过滤系统。
本章笔记：模式串和主串的匹配过程可以看成模式串在主串中不停地往后滑动。当遇到不匹配时，如何跳过一些肯定不会匹配的情况，将模式串往后多滑动几位，这样字符串匹配算法的性能就提高了。学习字符串匹配算法，除了字符串匹配问题是一种常见应用以外，学习各种字符串匹配算法也能锻炼程序员算法设计的水平和能力。
