首页 > 代码库 > 学渣乱搞系列之字符串滚动哈希

学渣乱搞系列之字符串滚动哈希

学渣乱搞系列之字符串滚动哈希

          by 狂徒归来

 

  我们假定字符串S = S1S2S3S4S5S6S7S8S9. 我们定义哈希函数为

  H(S) = (S1bm-1+S2bm-2+S3bm-3+...+Smb0)mod h.其中b是基数,相当于把字符串看成b进制数。

  b与h为合适的互素的常数。

  如何求取字符串内长度为m的一段的字符子串的哈希值?

  假定m = 3.

  先求取H([S1...S3]) =  S1b2+S2b1+S3b0.

  求取H([S2...S4]) = H([S1...S3])*b + S4 - S1*b3  = S2*b2 + S3*b1 + S4*b0.

  那么推导出来的滚动哈希公式就是:

  H(S[k+1...k+m]) = H(S[k...k+m-1])*b + Sk+m - Sk*bm.

  Rabin-Karp算法就是利用hash进行字符串匹配的算法。

学渣乱搞系列之字符串滚动哈希