前言：算法第二弹笔记来袭！主要内容为字符串匹配基础原理及简单算法。

字符串匹配基础

（1）BF算法。Brute Force的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。
（2）主串和模式串。在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。
（3）我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。
我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(nm)。
BF算法的时间复杂度很高，是O(nm)。
（4）RK算法。RK 算法的全称叫 Rabin-Karp 算法。思想：暴力对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串。
（5）RK算法思路：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
（6）RK算法实现：我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
（7）RK算法实现问题：我们设计的哈希算法是没有散列冲突的，也就是说，一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样。因为我们是基于进制来表示一个字符串的，你可以类比成十进制、十六进制来思考一下。实际上，我们为了能将哈希值落在整型数据范围内，可以牺牲一下，允许哈希冲突。哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。

字符串匹配之BM算法

（1）如何实现文本编辑器中的查找功能
（2）BM（Boyer-Moore）算法：包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。
（3）坏字符规则。BM算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。把这个没有匹配的字符叫作坏字符（主串中的字符）。继续拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 c 与模式串中的任何字符都不可能匹配。
不匹配后会进行滑动。滑动的位数的规律:把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。特别注意，如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。
（4）BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。
（5）好后缀规则。把已经匹配的后缀串，比如“bc”叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u}，那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置。
如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面。
（6）结论：BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM 算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现 BM 算法。

字符串匹配之KMP算法

（1）KMP算法：KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的。
（2）在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。
（3）好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。
（4）失效函数的next数组计算。
（5）假设a, b分别是主串和模式串；n, m分别是主串和模式串的长度。
空间复杂度：KMP算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。
时间复杂度：KMP算法的时间复杂度就是 O(m+n)。