首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是最简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
字符串匹配算法有很多种。例如简单、好理解的BF 算法和 RK 算法。还有比较难理解、但更加高效的BM 算法和 KMP 算法。
字符串匹配算法也可以分为单模式串匹配算法，也就是一个串跟一个串进行匹配。还有多模式串匹配算法，也就是在一个串中同时查找多个串，它们分别是 Trie 树和 AC 自动机。
本节主要讲述两个算法：RK 算法和 BF 算法。前者主要是对后者的改进，巧妙借住了前面说过的哈希算法，让匹配的效率有很大的提升。那RK 算法是如何借助哈希算法来实现高效字符串匹配的呢？
BF 算法
BF算法（Brute Force）中文叫作暴力匹配算法，也叫朴素匹配算法。这种算法的字符串匹配方式很“暴力”，简单、好懂但是性能不高。
首先介绍两个概念——主串和模式串。比如，我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。主串的长度记作n，而模式串的长度记作m，n>m。
BF算法的思想为：在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。如下所示：
在极端情况下，主串是“aaaaaa………..aaaaaaa”。模式串为”aaaaab”，我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。尽管理论上，时间复杂多很高，但是实际上却是一个比较常用的字符串匹配算法。
- 实际中，大部分情况，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，大部分情况下算法的执行效率都优于最坏情况时间复杂度。
- 该算法实现非常简单，不容易出错，bug也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的KISS（Keep it Simple and Stupid）设计原则。
RK算法
RK 算法的全称叫 Rabin-Karp 算法。在BF算法中，每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。
RK算法的思路为：通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如相等，则说明匹配上了（后面再说哈希冲突的问题）。因为哈希值是一个数字，数字比较是否相等是非常快速的。
但是若使用哈希算法计算子串哈希值时仍然需要遍历子串中的每个字符。那么算法的整体效率仍然没有提高。
我们需要设计一个高效的哈希算法。假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。
如下所示，在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，我们只需要把进位从 10 改成 26 就可以。下面假设字符串中只包含 a ～ z这26个小写字符。
这种哈希算法，在主串中，相邻两个子串的哈希值的计算公式有一定关系。如下图所示：
从这个例子中，我们可以发现这样的规律：相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值。如果用公式表示的话，如下所示：
不过，其中 26^(m-1) 这部分的计算，可以通过查表的方法提高效率。将这些计算结果事先存在长度为 m 的数组中，公式中的“次方”就对应数组的下标。当我们需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。
那么 RK 算法的时间复杂度到底是多少呢？
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分为可以设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 $O(n)$。第二部分模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 $O(1)$，总共需要比较 $n-m+1$ 个子串的哈希值，所以，这部分的时间复杂度也是 $O(n)$。所以，RK 算法整体的时间复杂度就是 $O(n)$。
当然，如果模式串很长，相应的主串中的子串也会很长。通过上面的哈希算法计算得到的哈希值就可能很大。如果超过了计算机中整型数据怎么办呢？
上面的哈希算法是没有涉及到散列冲突的。也就是一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样。实际上，为了能将哈希值落在整型数据范围内，可以牺牲一下，允许哈希冲突。这时，怎么设计哈希算法呢？
例如假设字符串中只包含 a～z 这 26 个英文字母，每一个英文字母对应一个数字，比如 a 对应1，b 对应2，以此类推，z 对应26。可以把字符串中每个字母对应的数字相加，最后得到为哈希值。这时哈希算法产生的哈希值的数据范围就相对小很多了。
不过这种哈希算法的哈希冲突概率也挺高的。当然，也有更加优化的方法，比如将每一个字母从小到大对应一个素数，而不是 1，2，3……这样的自然数，这样冲突的概率就会降低一些。
但是散列冲突情况下，还有一个问题：子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。所以遇到子串和模式串的哈希值相等时，只需要再对比一下子串和模式串本身就好了。
所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。但是一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。
解答开篇 & 内容小结
本节讲了两种字符串匹配算法，BF 算法和 RK 算法。
BF 算法是最简单、粗暴的字符串匹配算法，它的实现思路是，拿模式串与主串中是所有子串匹配，看是否有能匹配的子串。所以，时间复杂度也比较高，是 $O(n*m)$，n、m 表示主串和模式串的长度。不过，在实际的软件开发中，因为这种算法实现简单，对于处理小规模的字符串匹配很好用。
RK 算法是借助哈希算法对 BF 算法进行改造，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间。所以，理想情况下，RK 算法的时间复杂度是 $O(n)$，跟 BF 算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 $O(n*m)$。
课后思考
本节主要讲的是一维字符串的匹配方法。假设有下面这样一个二维字符串矩阵（图中的主串），如何在其中查找另一个二维字符串矩阵（图中的模式串）呢？
假设二维主串和模式串的维度分别是 m*n 和 i*j，横向在[0, m-i]，纵向在[0, n-j]取起始点，然后取同样的子串窗口对比，共有(m-i+1)*(n-j+1)个子串。
