这篇文章主要讲的字符串的匹配算法,在本文中我将向大家介绍RK算法。我想在此之前很多的人应该都有了解BF算法吧，BF全称Brute Force,翻译过来就是暴力算法，相关案例在我之前写的文章力扣——统计只差一个字符的子串数目可以体现出来。由于这种方法消耗时间复杂度比较大，所以经常在实际开发中不太实用。
1.RK算法BF算法与RK算法的区别：
BF算法只是简单粗暴地对两个字符串的所以字符依次作比较，而RK算法比较的是两个字符串的哈希值。
比较哈希表是什么意思呢?用过哈希表的朋友都知道，每一个字符都可以通过某一种哈希算法，转换成一个整数型，这个整数型就是hashcode;
hashcode=hash(String)
如：
给定如下字符串和模式字符串（假定字符串只包含26小写字母）：
主串： abbcefgh
模式串: bce
第一步.我们需要生成模式串的hashcode
由于生成hashcode的算法很多，在我们这，采用按位相加
如：把a当成1，b当成2......然后把字符串的所以字符相加，相加的结果就是它的hashcode.
hash("bce")=2+3+5=10;
第二步：生成主串当中第一个等长子串的hashcode
由于主串通常情况要长于模式串，如果你把整个主串的所以字符全部转化成hashcode，这样比较是没有意义的，我们要比的是和模式串等长的hashcode的值。
即：
hash("abb")=5;
主串： a b b c e f g h
主串的第一个与模式串等长的字符hashcode值为5；
模式串： b c e hashcode=10;
第三步：比较两个hashcode.
显然5不等于10，，说明第一个字串不匹配。我们继续下一轮比较。
第四步：生成主串当中第二个等长子串的hashcode.
hash("bbc")=7
第五步，比较两个hashcode;
显然7≠10，说明模式串和第二个字串不匹配，我们继续下一轮比较。
第六步，生成主串当中第三个等长子串的hashcode.
hash("bce")=2+3+5=10;
第七步,比较两个hashcode;
10=10,两个hashcode值相等！这样是否说明两个字符串也相等呢?
别高兴得太早，由于存在hash冲突的可能，我们还要进一步验证。
第八步,逐个比较两个字符串；
hashcode的比较只是初步验证，之后我们还要跟BF算法那样，两个字符串逐个比较，最终判断两个字符是否匹配，最后得出结论，模式串 bce是主串abbcefgh的字串，第一次出现的下标是2.
到这大家会不会有个疑问，认为RK算法的时间复杂度和BF算法时间复杂度相同。都是O(mn);
注：m是主串的长度，n是模式串的长度。
这个问题提的好！对于字串的哈希操作计算并不是相互独立的，从第二个字串开始，每个字串的哈希操作都可以上一个子串进行简单增量计算来得到。
什么意思呢？让我们再来看一个例子：
主串：a b b c e f g d e a q f w
hash("abbcefg")=26;
上图中，已知字串的abbcefg的hashcode是26,那么如何计算下一个字串，也就是bbcefgd的hashcode呢?
我们没必要把子串的字符重新进行叠加运算，而是可以采用一个更加简单的方法。由于新子串的前一个少了a,后面多了个d,所以:
新hashcode=旧hashcode-1+4=26-1+4=29;
再下一个子串bcefgde的计算也一样。
新hashcode=旧hashcode-2+5=29-2+5=32;
代码测试：
public class Demo {
public static int rabinKarp(String str,String pattern){
// 主串的长度
int m=str.length();
// 模式串的长度
int n=pattern.length();
// 计算模式串的hash值
int patternCode=hash(pattern);
// 计算主串中第一个和模式串等长的子串的hash值
int strCode=hash(str.substring(0,n));
//用模式串的hash值和主串的局部hash值进行比较。
for(int i=0;i<(m-n+1);i++){
// 如果匹配，则进行精准比较
if((strCode==patternCode)&&compareString(i,str,pattern)){
return i;
}
// 如果不匹配，计算主串中相邻子串的hash值
if(i<(m-n)){
strCode=nextHash(str,strCode,i,n);
}
}
return -1;
}
private static int hash(String str){
int hashCode=0;
for(int i=0;i
RK算法计算模式串的hashcode需要访问n个字符，计算第一个子串的hashcode也需要访问n个字符，后续子串的hashcode是增量计算，有m-n次，所以总的时间复杂度是O(m+n);
RK算法的缺点在于哈希冲突，每一次出现哈希冲突的时候，RK算法都要对字串和模式串进行逐个字符串的比较，如果冲突太多，RK算法就退化成BF算法了。
下一章，我将会想大家介绍另一种字符串匹配算法（KMP算法），这种算法不但高效，而且还稳定。那我们下期再见！！
