什么是字符串匹配
字符串匹配是主串返回模式串在主串中出现的位置，类似于mysql中FIND_IN_SET、LOCATE、POSITION、INSTR等函数的作用。
比如主串：abbcefgh，模式串：bce，匹配结果为cde第一次出现的下角标2。
Brute Force（暴力算法）
该算法原理很简单，旨在从头到尾一次一次的比较模式串是否在主串中出现，算法思路如下
第一轮：
主串首字母和模式串首字母不一致开始下一轮
第二轮：
模式串后移一位，比较模式串首字母和主串第二位字母，比较结果一直
然后比较模式串第二位和主串第三位字母是否一致，结果为否，进行下一轮比较
第三轮：
和第二轮比较一样，依次比较每一位字符，直到完全一致，则认为该主串为该模式串的母串，返回下角标2
主串若不包含母串，则返回-1
缺点：很明显，该算法如同其名字一样，直接暴力，但是效率很差，如果主串的“匹配串”在靠后的位置，则需要检索整个主串。
RK算法（Rabin-Karp）
该算法是对暴力算法的一种改进，是由其两位发明者的名字来组合命明的。
该算法比较的是两个字符串的哈希值（hash value）
用过哈希表的都应该知道，每一个字符串都可以通过某种哈希算法转换成一个整数，这就是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一致
但是hashcode一致并不代表该hashcode代表的字符串一致，所以为了避免hashcode冲突，则需要再比较此处的字符串是否相等来确定最终的结果。
注意：我们并不需要每次计算每组字符串的hashcode，只需要将当前hashcode减去上一个字符的hashcode值，然后再加上后一个字符的hashcode值即可。
代码如下：
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));
}
相对于暴力算法，RK算法使用hashcode比较，子串的复杂度为O(n)，由于后续的子串hash是增量计算，所以总的时间复杂度仍是O(n)，其避免了大量的字符串比较，不足在于会有hashcode冲突，还是需要做一定的字符串比较，如果hashcode生成算法选择不合适，导致冲突过多的话，相对于暴力算法就会失去优势。