「算法」字符串查找之 Rabin Karp 算法

暴力算法

??在讲Rabin Karp算法之前，我们在字符串查找子串中可以使用是暴力字符串匹配，但是使用暴力的话，效率就会非常慢，因为他需要比对文本和模式串的每一个字符。
例如问题：在abcde中查找cde：

• 第一步：abc与cde比较
• 第二步：bcd与cde比较
• 第三步：cde与cde比较

??这样查找的缺点是：在每一步的比较中，他只能一个个字符串比较，要花费O(n?)。浪费很多时间。

代码

public class Solution {/** @param source: A source string* @param target: A target string* @return: An integer as index*/public int strStr2(String source, String target) {if(source == null || target == null){return -1;}for(int i = 0 ; i < source.length() - target.length() + 1; i++){int j = 0 ;for(j = 0 ; j < target.length(); j++){if(source.charAt(i + j) != target.charAt(j)){break;}}if(j == target.length()){return i;}}return -1;}
}

??如何能解决暴力的时间复杂度太高的问题呢？

Rabin-Karp算法

??思考：若能不用字符串与字符串比较，而是使用整数与整数比较，那么就能是实现时间复杂度从O(n?) => O(1) 。
隆重介绍：
Rabin-Karp算法！
它在解决“一个字符串中定位子串的位置问题“中将时间复杂度直接降为O(1)。
Rabin-Karp思路：将字符串变成整数来比较，可以使用Hash Function来理解。在Hash Function中，最重要的就是把任何给进来的key，不管是String,int,double……反正任何类型都可以，只要是能用几个字节表示的数据都可以变成一个整数。
通常的Hash Function就是使用进制转换来实现：

Eg：a b c d e
=a * 31? + b * 31? + c * 31? + d * 31? + e *31?
（1）大家会觉得奇怪，为什么这个a b c d e这些字符可以与数字相乘，其实是可以的，在程序中，任何一个字符都有对应的ACSII码。直接与数字相乘也不需要做任何的转换，系统会帮你做转换
（2）为什么乘31，其实乘任何一个数都可以，我们把31这个数叫做经验值【就是在进制转换中常用的基数中效率最高的数】
（3）字符串对应固定的整数，但是反过来整数不一定对应一个固定的字符串。但这个没关系，因为Hash Function只要保证key->value是唯一的就行。
（4）这个结果可能会很大，我们可以对这个结果取模，比如模10?，这个数是都可以的，你也可以模10?，这个模的数越大，那么它的冲突就越小。eg.模2，那么一半都是0，一半都是1，那么冲突就很大 。所以一般会模较大的数。

接着我们来分析如何在abcde中查找cde：

首先分析：如何从abc–>bcd:
第一步：bc是不变的，故我们可以先将abc的Hash Function算出来，然后把d加进去，这时候abcd的Hash code变成num0 = [(a * 31? + b * 31? + c)* 31+d]% 10?
第二步：把a从刚刚算的Hash code中剪掉，然后再取模，num1 =num0 - a * 31? num2 = num1 % 10?
第三步：分析有什么问题：

1. 在num1中，num0会小于a * 31?，解决办法：a * 31?后取完模在于num0做减法。
2. a * 31?模后可能还是会大于num0，解决办法在计算完num1后在加上10?，确保最后得出的数是整数。

其次分析：当我们一个个移动，找到cde时，那么我们还要判断这个cde是不是我们要的cde。因为我们基于的假设是：如果hash function算出的hash code是唯一的，那么就可以用整数去代表字符串，但是有可能不唯一，比如：同一个整数对应两个字符串。这是hash function无法保证的，这也是hash function的特性。所以我们还得再来一次判断，将我们通过整数找到的cde与题目中的cde做一个一个字符的比较。

时间复杂度分析:因为我们在移动比较的时候都是O(1),而只有在当我们找到对应的整数时,我们才会花费O(n)的时间复杂度去查找这个整数对应的字符串是否是我们需要的字符.但是这种比较少之又少,我们加速了大部分的比较时间,只有答案的阶段是O(n),故时间复杂度就像当于O(1+n)

好处：在abc变成bcd的过程中，把d添加进去 => O(1)，把a删除 => O(1)，故用Rabin-Karp来查找子串，那么时间复杂度就为O(1)。这个算法中当两个字符串通过hash function算出的整数不一样，那么他们的字符串一定不一样，故这个算法就是加速了这个过程.

例题

或许大家对这个Rabin-Karp还是没有深刻的印象，我们来看一道题，这道题是Lintcode 594. strStr II
题目描述：

strStr在O（n + m）时间内实现功能。
strStr返回源字符串中目标字符串的第一个索引。目标字符串的长度为m，源字符串的长度为n。
如果源中不存在目标，则返回-1。

代码实现

public class Solution {public int BASE = 1000000;/** @param source: A source string* @param target: A target string* @return: An integer as index*/public int strStr2(String source, String target) {// write your code hereif(source == null || target == null){return -1;}int m = target.length();//空串if(m  == 0){return 0;}//算a * 31 ^ mint power = 1;for(int i = 0 ; i < m ; i++){power = (power * 31) % BASE;   //一边乘一边模，保证不越界}//算目标串的hash codeint targetCode = 0 ;for(int i = 0 ; i < m ; i++){targetCode = (targetCode * 31 + target.charAt(i)) % BASE;}//当前的hash codeint hashCode = 0;for(int i = 0 ; i < source.length(); i++){//abc + dhashCode = (hashCode * 31 + source.charAt(i)) % BASE;if(i < m - 1){continue;}//abcd - aif(i >= m){hashCode = hashCode - (source.charAt(i - m)) * power % BASE;if(hashCode < 0){hashCode += BASE;}}//double check the stringif(hashCode == targetCode){//这个结尾是个开区间所以要使用i+1if(source.substring(i - m + 1,i+1).equals(target)){return i-m+1;} }}return -1;}
}

若对Rabin Karp 算法还有所疑惑，可以在评论区提出你的疑惑
祝我们都成为优秀的学习冠军！