字符串算法
一、BF算法
Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。
我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。
算法思想：在主串中，检查起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。
时间复杂度：最坏情况时间复杂度是 O(n*m)。
二、RK算法
Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的
我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
不过，通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高，有没有方法可以提高哈希算法计算子串哈希值的效率呢？
比如：我们的字符串只有 a-z 这些字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。然后计算出主串中 m 长的字符串的值，而且可以把 26^(m-1) 这部分的计算事先做好放在数组中直接用。
- 时间复杂度：整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。第二部分，模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。
刚才设计的哈希算法没有哈希冲突，但是可能出现数字太大，超过整形数据表示范围。我们可以允许一些哈希冲突，比如 我们用素数来表示 a-z 这些字母 等等
三、BM算法
在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）