Rabin-Karp

先进行名词的说明:源串(S1)长度为n,子串(S2)长度为m

暴力之所以会慢，主要在于S1匹配了S2的第一个字符后，还要进行至多m-1个字符的判断。

如果能将S2映射到某个数字num1，S1每次也得到当前m长度字符串的映射数字num2，判断num1和num2是否相同（一次操作）即可快速判断两个字符串可能相同。

上面说法需要注意两个问题：

1. S1每次计算m长度字符串的映射数字需要足够快，必须仅做一次操作
2. num1和num2相同仅能判断两个字符串可能相同，还需要进行字符串每一位的判断

如何快速计算字符串的映射数字呢？

我们假设 s1="jijiaxing" s2="jia"，字符对应的数字采用ASCII值，取ASCII字符集长度M为128

左部为高位，最高位hash值为s2[0].charCodeAt(0)*(128**(m-1))(**在js中表示指数运算)

计算s2("jia")对应的hash值：

1. hash("j")=106
2. hash("ji")=hash("j")*128+105=13673
3. hash("jia")=hash("ji")*128+97=1750241

我们可以添加或者删减一个字符，快速得到新字符串的hash值

hash("iax")=(hash("jia")-hash("j")*(128**2))*128+120=(1750241-106*16384)*128+120=1732856

这样我们就可以先计算s1前m长度字符串的hash值，hash值一致再逐个比较，否则删去第一个字符，从s1再加一个字符，继续比较。。

前面的操作，我们没有做 mod 运算，当s2长度计算出来的hash值过大的时候，(js大数运算相对耗时)，我们需要对该值取余散列。假设哈希表长度Q为 10007

于是前面的操作hash("jia")变成:

1. hash("j")=106%10007=106

2.  hash("ji")
    =(106*128+105)%10007
    =((106*128)%10007+105%10007)%10007
    =(((106%10007)*(128%10007))%10007+105%10007)%10007
    =((hash("j")*128)%10007+105%10007)%10007
    =((hash("j")*128)+105)%10007
    =3666
   

   即，hash("ji")=((hash("j")*128)+105)%10007
3. 同理，hash("jia")=(hash("ji")*128+97)%10007=9023

增减字符串的计算过程如下：

hash("iax")
=(105*(128**2)+97*128+120)%10007
=((105*(128**2)+97*128)%10007+120%10007)%10007
=(((105*128+97)%10007*128%10007)%10007+120%10007)%10007
=(((106*(128**2)+105*128+97-106*(128**2))%10007*128%10007)%10007+120%10007)%10007
=((((106*(128**2)+105*128+97)%10007-(106*(128**2))%10007+10007)%10007*128%10007)%10007+120%10007)%10007
//用hash("jia")替换
=((((hash("jia")-(106*(128**2))%10007+10007)%10007*128%10007)%10007+120%10007)%10007
=(((hash("jia")+(10007-(106*(128**2))%10007))%10007*128%10007)%10007+120%10007)%10007
//化简10007-(106*(128**2))%10007
//=(10007-(106*(128**2))%10007)%10007
//增加一个10007倍数的值，不影响
//=(10007-(106*(128**2))%10007+105*10007)%10007
//=(106*10007-106*(128**2)%10007)%10007
//=(106*(10007-128**2%10007))%10007 
=((((106*(128**2)+105*128+97)%10007+(106*(10007-128**2%10007))%10007)%10007*128%10007)%10007+120%10007)%10007
=(((hash("jia")+(106*(10007-128**2%10007))%10007)*128)%10007+120%10007)%10007
=(((hash("jia")+(106*(10007-128**2%10007))%10007)*128)+120)%10007
// 计算本例的固定值10007-128**2%10007=3630
=(((hash("jia")+106*3630%10007)*128)+120)%10007
=(((9023+106*3630%10007)*128)+120)%10007
=1645

计算的时候，采用该式子： (((hash("jia")+106*3630%10007)*128)+120)%10007

以上用到了 同余定理

A*B % C = (A%C * B%C)%C
(A+B)%C = (A%C + B%C)%C
(A-B)%C = (A%C - B%C + C)%C // js运算中 -2%5=-2而不是3 故这里我们需要补上C,让差大于0 

下面给出Rabin-Karp的简单实现：

var Q = 10007
var M = 128
function getHash(str,len){
  var val = 0
  for(var i=0;i<len;i++){
    val=(val*M+str[i].charCodeAt(0))%Q
  }
  return val
}
//逐个比较相同长度字符串,s1从index位置开始取
function compare(s1,s2,offset){
  for(var i=0;i<s2.length;i++){
    if(s1[i+offset]!==s2[i])return false
  }
  return true
}
function match(s1,s2){
  var n = s1.length
  var m = s2.length
  if(n<m)return -1
  var s2Hash = getHash(s2,m)
  // 一个固定值
  var fix = Q-M**(m-1)%Q
  var curHash = getHash(s1,m)
  if(curHash===s2Hash&&compare(s1,s2,0))return 0
  for(var i=m;i<s1.length;i++){
    var offset = i-m+1
    curHash = (((curHash+(s1.charCodeAt(i-m))*fix%Q)*M)+s1.charCodeAt(i))%Q
    if(curHash===s2Hash&&compare(s1,s2,offset))return offset
  }
  return -1
}
//match("jijiaxing","jia")=2

效率

理论时间复杂度为O(n*m),但是由于hash不一致能排除大部分情况，故实际复杂度大概在O(n+m)

参考

Rabin-Karp指纹字符串查找算法