漫画：什么是字符串婚配算法？
————— 第二天 —————
什么意思呢？让我们来举一个例子：
在上图中，字符串B是A的子串，B第一次在A中显现的地点下标是2（字符串的首位下标是0），以是前往 2。
我们再看另一个例子：
在上图中，字符串B在A中并不存在，以是前往 -1。
为了一致看法，在后文中，我们把字符串A称为主串，把字符串B称为形式串。
小灰的想法简便粗暴，让我们用底下的例子来演示一下：
第一轮，我们从主串的首位开头，把主串和形式串的字符逐一比力：
显然，主串的首位字符是a，形式串的首位字符是b，两者并不婚配。
第二轮，我们把形式串后移一位，从主串的第二位开头，把主串和形式串的字符逐一比力：
主串的第二位字符是b，形式串的第二位字符也是b，两者婚配，持续比力：
主串的第三位字符是b，形式串的第三位字符也是c，两者并不婚配。
第三轮，我们把形式串再次后移一位，从主串的第三位开头，把主串和形式串的字符逐一比力：
主串的第三位字符是b，形式串的第三位字符也是b，两者婚配，持续比力：
主串的第四位字符是c，形式串的第四位字符也是c，两者婚配，持续比力：
主串的第五位字符是e，形式串的第五位字符也是e，两者婚配，比力完成！
由此取得后果，形式串 bce 是主串 abbcefgh 的子串，在主串第一次显现的地点下标是 2：
以上就是小灰想出的处理方案，这个算法有一个名字，叫做BF算法，是Brute Force（暴力算法）的缩写。
上图的情况，在每一轮举行字符婚配时，形式串的前三个字符a都和主串中的字符相婚配，不休反省到形式串最初一个字符b，才发觉不婚配：
如此一来，两个字符串在每一轮都必要白白比力4次，显然十分糜费。
假定主串的长度是m，形式串的长度是n，那么在这种极度情况下，BF算法的最坏时间繁复度是O（mn）。
————————————
比力哈希值是什么意思呢？
用过哈希表的伙伴们都晓得，每一个字符串都可以经过某种哈希算法，转换成一个整型数，这个整型数就是hashcode：
hashcode = hash（string）
显然，干系于逐一字符比力两个字符串，仅比力两个字符串的hashcode要容易得多。
给定主串和形式串如下（假定字符串只包含26个小写字母）：
第一步，我们必要天生形式串的hashcode。
天生hashcode的算法多种多样，好比：
按位相加
这是最简便的办法，我们可以把a当做1，b当做2，c当做3……然后把字符串的一切字符相加，相加后果就是它的hashcode。
bce = 2 + 3 + 5 = 10
但是，这个算法固然简便，却很约莫产生hash分歧，好比bce、bec、cbe的hashcode是一样的。
转换成26进制数
既然字符串只包含26个小写字母，那么我们可以把每一个字符串当成一个26进制数来盘算。
bce = 2*(26^2) + 3*26 + 5 = 1435
如此做的利益是大幅变小了hash分歧，缺陷是盘算量较大，并且有约莫显现超出整型范围的情况，必要对盘算后果举行取模。
为了便利演示，后续我们接纳的是按位相加的hash算法，以是bce的hashcode是10：
第二步，天生主串中间第一个等宗子串的hashcode。
由于主勾通常要善于形式串，把整个主串转化成hashcode是没故意义的，仅有比力主串中间和形式串等长的子串才故意义。
因此，我们首教师成主串中第一个和形式串等长的子串hashcode，
即abb = 1 + 2 + 2 = 5：
第三步，比力两个hashcode。
显然，5！=10，分析形式串和第一个子串不婚配，我们持续下一轮比力。
第四步，天生主串中间第二个等宗子串的hashcode。
bbc = 2 + 2 + 3 = 7：
第五步，比力两个hashcode。
显然，7！=10，分析形式串和第二个子串不婚配，我们持续下一轮比力。
第六步，天生主串中间第三个等宗子串的hashcode。
bce= 2 + 3 + 5 = 10：
第七步，比力两个hashcode。
显然，10 ==10，两个hash值相称！这对否分析两个字符串也相称呢？
别兴奋的太早，由于存在hash分歧的约莫，我们还必要进一步验证。
第八步，逐一字符比力两字符串。
hashcode的比力只是开头验证，之后我们还必要像BF算法那样，对两个字符串逐一字符比力，终极推断出两个字符串婚配。
最初得出结论，形式串bce是主串abbcefgh的子串，第一次显现的下标是2。
什么意思呢？让我们再来看一个例子：
上图中，我已知子串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 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值比力。
//假如婚配，则举行准确比力；假如不婚配，盘算主串中相邻子串的hash值。
for (int i=0; i<m-n+1; i++) {
if(strCode == patternCode && compareString(i, str, pattern)){
return i;
}
//假如不是最初一轮，更新主串从i到i+n的hash值
if(i<m-n){
strCode = nextHash(str, strCode, i, n);
}
}
return -1;
}
private static int hash(String str){
int hashcode = 0;
//这里接纳最简便的hashcode盘算办法：
//把a当做1，把b中间2，把c中间3.....然后按位相加
for(int i = 0; i < str.length; i++) {
hashcode += str.charAt(i)-'a';
}
return hashcode;
}
private static
int nextHash(String str, int hash, int index, int n){
hash -= str.charAt(index)-'a';
hash += str.charAt(index+n)-'a';
return hash;
}
private static boolean compareString(int i, String str, String pattern)
{
String strSub = str.substring(i, i+pattern.length);
return strSub.equals(pattern);
}
public static void main(String[] args)
{
String str = "aacdesadsdfer";
String pattern = "adsd";
System.out.println("第一次显现的地点:" + rabinKarp(str, pattern));
}
本文为步骤员小灰（ID：chengxuyuanxiaohui）投稿。
