暴力匹配算法(Brute Force)
主串中检查起始位置分别是0、1、2...n-m且⻓度为m的n-m+1个子串，查找跟模式串相匹配
此算法字符串匹配方式比较简单、好懂、暴力，但相应的性能不高，也叫朴素匹配算法
名词解释
我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。
我们把主串的⻓度记作n，模式串的⻓度记作m。因为是在主串中查找模式串，所以n>m
在极端情况下，如主串为“aaaaa...aaaaaa”，模式串是“aaaaab”。
我们每次都比对m个字符，要比对n-m+1次，所以这种算法的最坏情况时间复杂度是O(n*m)
实际开发绝中大部分情况下常用的算法，原因如下:
1.实际的软件开发中，大部分情况下，模式串和主串的⻓度都不会太⻓
且每次模式串与主串中的子串匹配时，当不能匹配时就停止不需要把剩下字符都比对完
2.朴素字符串匹配算法思想简单，代码实现也非常简单。遵循KISS原则
Rabin-Karp算法
暴力匹配算法BF升级版
通过哈希算法对主串中n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。
若某子串的哈希值与模式串相等，则说明对应的子串和模式串相匹配(暂不考虑哈希冲突)。
因为哈希值是数字，数字比较是否相等是非常高效，所以模式串和子串比较的效率就提高
通过哈希算法计算子串的哈希值时需要遍历子串中每个字符。
尽管模式串与子串比较的效率提高了，但算法整体的效率并没有提高
优化方案: 重点在于哈希算法设计
主串包含字符个数K，把子串先转为K进制数，再转十进制作为哈希值
主串中相邻两个子串的哈希值的计算公式有一定关系
相邻两个子串s[i-1]和s[i]，对应的哈希值计算公式有交集，具体如下图:
(子串在主串中的起始位置i，子串⻓度m)
提前计算26次方值且存储在⻓度为m数组中，“次方”对应数组下标，使用时根据下标访问
时间复杂度
整个RK算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较
第一部分，通过特殊哈希算法，扫描一遍主串计算所有子串哈希值，时间复杂度为O(n)
第二部分，模式串哈希值与单个子串哈希值比较时间复杂度为O(1)，总时间复杂度为O(n)
整个RK算法时间复杂度为O(n)
哈希冲突
如果哈希算法设计存在哈希冲突，冲突时再对比下模式串和子串本身
哈希算法冲突概率要控制，如果存在大量冲突，导致RK算法时间复杂度退化
