0x00 Introduction

本文是对Rolling Hash (Rabin-Karp Algorithm)的一个翻译or总结，毕业设计的时候需要用到，加上山里过年有一点无聊，就赶紧看一看。

文章很短，就是对Rolling Hash这一算法的介绍，所谓这篇博客大概会更偏向对文章的翻译。

0x01 算法基础

目标:假设我们有一个字符串S和一个模式字符串P，我们想要确定是否S中包含有P，即P是S的一个子串。

字符串(String)可以看作是一个字符(Char)数组，而字符又可以根据使用的编码方式(比如ASCII,Unicode)对应的特定数值来解释为整数(Integar)。这意味着我们可以将字符串看作是一个整数数组。

基于这一思想，我们可以将字符串A和B的比较转换成两个整数数组的比较，即遍历A和B，使得A[i]==B[i]对任意i成立。但是这种字符串比较算法所需时间取决于字符串长度，即比较两个长度为n的字符串需要O(n)的时间。而Hash算法通常也是遍历整个字符串，也需要O(n)的时间。

基于该思想，可以实现字符串的模式匹配

0x02 Method

设P长度为L，S长度为n。

  1. 对P哈希得到h(P) O(L)
  2. 遍历S中每个长度为L的子串，分别对其哈希并与h(P)比较 O(nL)
  3. 将哈希值与h(P)相等的子串与P进行字符串比较，避免哈希碰撞 O(L)

该算法的时间复杂度是O(nL)。我们可以使用Rolling Hash来改进这一算法。这些长度L的子串相邻子串具有极大的重叠部分。比如，字符串”algorithms”长度为5的子串中，前两个子串”algor”和”lgori”重叠了”lgor”，且在两个子串中各自占据了绝大部分，这使得我们能够使用Rolling Hash来利用此特点节约大量计算。

0x03 “数值”举例

我们直接用整数数组来代替字符串来举例： 

1
2
P = [9,0,2,1,0]
S = [4,8,9,0,2,1,0,7]

则S的长为5的子串为：

1
2
3
4
S0 = [4,8,9,0,2]
S1 = [8,9,0,2,1]
S2 = [9,0,2,1,0]
...

我们的hash算法为：

$h(k) = (k[0]10^4+k[1]10^3+k[2]10^2+k[3]10^1+k[4]10^0)\,mod\,m$

换句话说，我们直接将各子串转换成一个5位整数，然后用这个整数mod m。h(P) = 90210 mod m，h(S0) = 48902 mod m，h(S1) = 90210 mod m。当我们使用这种hash方法，我们可以使用h(S0)来计算出h(S1)。

$ h(S_i+1) = [(h(S_i)−(10^5∗first\,digit\,of\,S_i))∗10 +next\,digit\,after\,S_i]\,mod\,m $

以上是base = 10,L=5的一个例子，将base和L回代：

$h(k) = (k[0]b^{L−1}+k[1]b^{L−2}+k[2]b^{L−3}…k[L−1]b^0)\,mod\,m$

0x04 improved Method

使用Rolling Hash进行字符串比较

  1. 对P哈希得到h(P) O(L)
  2. 对S的第一个L长度子串哈希 O(L)
  3. 使用Rolling Hash 计算随后的子串，和h(P)的hash值比较 O(n)
  4. 将哈希值与h(P)相等的子串与P进行字符串比较，避免哈希碰撞 O(L)

0x05 常见的子串问题

通常我们还会遇到在两个长度为n的长字符串S，T中查找是否有共同的长为L的子串的问题。该问题可以通过对上述Method稍加修改解决:

  1. 对S的第一个L长度子串哈希 O(L)
  2. 使用Rolling Hash 计算S中随后的子串，加入一张hash表中 O(n)
  3. 对T的第一个L长度子串哈希 O(L)
  4. 使用Rolling Hash 计算T中随后的子串，对每个子串，检查hash表中判断与S中的子串是否发生hash碰撞 O(n)
  5. 将hash值相等的两个子串进行字符串比较。 O(L)

To be continued …

暂时撸到这里，关于最后第四步的O(n)，我还是不太理解的，文章的解释是要限制次数，这篇博客就不多说明了，改日再研究~