Rabin-Karp算法

理论解析

我们这里记录笔记主要是为了便于理解，所以假设：\(\sum = \{0,1,\cdots,9\}\)，我们假设每个字符以\(d = |\sum|\)。这里\(d=10\)，我们便可以用长度为\(k\)的十进制数来代表由\(k\)个连续的字符组成的字符串。Eg. 字符串31415对应十进制数\(31415\)。

给定模式串\(P[1\cdots m]\)，给定文本串\(T[1\cdots n]\)。

我们分别假设\(P\)对应的十进制值为\(p\)，对于\(T\)我们考虑的不是整个串的值，我们考虑的是它能否和\(P\)进行匹配，所以我们考虑的是\(t_s\)代表子串\(T[s+1, s+m]\)的十进制值，显然当且仅当\(P =T[s+1,s+m]\)时，\(p = t_s\)。那么，我们现在就要考虑如何高效的计算\(p,t_s\)。

注意，此时我们还没有考虑\(p, t_s\)过大的问题。

对于\(p\)，我们可以使用前缀和进行操作，\(p_i = P[i] + 10\times p_{i-1}\)，最后结果就是\(p_m\)。

对于\(t_s\)的计算，我们同样可以使用前缀和的思想\(t_{s+1} = 10 (t_{s} - 10^{m-1}T[s+1]) + T[s+m+1]\)。

我们只需要预处理\(10^{m-1}\)然后便可以在\(\mathcal{O}(n)\)的时间内完成对于\(t_s\)的计算。

到目前为止，我们都默认\(p, t_s\)都是较小的数字，因为当它们的值大到一定程度时，我们在\(p,t_s\)上进行一些算数操作就不再是常数时间的了。因此，我们如何解决这个问题呢？

其实解决这个问题很简单，我们只需要选择一个合适的模数\(q\)来计算\(p\)和\(t_s\)的模。

对于\(p\)来说，我们只需要直接对每个数计算模\(q\)的值即可。

对于\(t_s\)来说，我们则需要进一步考虑如何修改公式，其实只有\(10^{m-1}\)需要进行处理，则处理为\(h\equiv 10^{m-1} \% q\) 代表最高位。则公式可以改为：\(t_{s+1} = (10(t_s - h T[s+1]) + T[s + m + 1])\bmod q\)

但是，这样直接取模仍然存在一定问题：因为\(t_s \equiv p \pmod{q}\)并不能说明\(t_s = p\)，同时如果\(t_s \neq p \pmod{q}\)那么必定存在\(t_s \neq p\)，从而确定偏移\(s\)是无效的。因此我们可以把\(t_s \equiv p \pmod{q}\)作为一个快速的测试来判断\(s\)是否为无效偏移，如果不能通过这个判断是否为无效偏移则需要进一步的朴素匹配来检测。

算法伪代码

\[\begin{array}{rl}
& \text{RABIN-KARP-MATCHER}(T,P,d,q) \\
1 & n = T.length\\
2 & m = P.length\\
3 & h = d^{m-1}\bmod q\\
4 & p = 0 \\
5 & q = 0\\
6 & \textbf{for } i =1 \textbf{ to } m\\
7 & \qquad p=(dp+P[i])\bmod q\\
8 & \qquad t_0 = (dt_0 + T[i]) \bmod q\\
9 & \textbf{for } s =0 \textbf{ to }n-m\\
10& \qquad \textbf{if } p==t_s \\
11& \qquad \qquad \textbf{if }P[1\cdots m] == T[s+1\cdots s+m]\\
12& \qquad \textbf{if } s<n-m\\
13& \qquad \qquad t_{s+1} = (d(t_s -T[s+1]h)+T[s+m+1])\bmod q\\
\end{array}
\]

时间复杂度分析

RABIN-KARP-MARCHER的预处理时间复杂度为：\(\Theta(m)\)，

然后，我们讨论最坏情况，那就比如是全部是相同的字符，这样的情况下我们需要的时间和朴素的字符串匹配时间相同为：\(\Theta((n-m+1)\times m)\)。

32. 2-2 如何扩展 Rabin-Karp 算法，使其能解决如下问题：如何在文本字符串中搜寻出给定的\(k\)个模式中的任何一个出现？起初假设所有 \(k\) 个模式都是等长的，然后扩展你的算法以适用于不同长度的模式。

答案：我们在伪代码的第10行，可以修改利用一个HashMap，其中键为某个模式的\(q_k\)，值为对应的字符串长度。这样可以在\(\mathcal{O}(m(n-m+1)\log k)\)时间内进行处理。

假如需要处理\(l_1, \cdots,l_k\)的不同长度的模式，我们只需要维护一个\(A\)数组，然后\(A[i]\)维护的是\(T\)的前\(l_i\)个字符\(\bmod q\)，然后在\(10\)行处进行循环处理和更新，这样复杂度变为\(O(k\max{(l_k)}(n-m+1))\)。