8.1. Rabin-Karp 字符串搜索算法 [Draft]¶

Rabin-Karp 算法基于一种可以想象成"字符串的完美散列函数"的东西。 我们假设字符串取自一个可能字符数为 \(C\) 的字母表。 用 \(s_0, s_1, \ldots s_{n-1}\) 表示字符串 \(S\) 中的字符。 假设我们有一个映射 \(c \rightarrow \hat{c}\)， 它把每个字符 \(c\) 关联为 \(0 \ldots c - 1\) 范围内的一个整数 \(\hat{c}\)。那么，"字符串的完美散列函数"为：

假设我们把字符串的这个值称为它的"幻数"。 实际上，它把每个字符串关联为基 \(C\) 数系中的一个唯一数。 然而，没有什么事是完美的——这些字符串的幻数会非常快地变得很大。 因此，Rabin-Karp 用于计算字符串幻数的以下子算法 （它本身也被称为 Horner 多项式求值算法）通过使用 \(mod\) 运算符 来避免溢出，从而考虑到了这一点。

用于计算字符串的 Rabin-Karp"幻数"的 Horner 方法算法幻灯片

为了检验你对该"幻数"计算的理解，请做下面的练习， 在一个简单情况下用 Horner 方法计算字符串的"幻数"。

由于 Horner 方法无法真正为每个字符串计算出唯一的幻数， Rabin-Karp 算法必须允许两个不同的字符串具有相同的幻数。 实际上，这种情况代表一种"误报"，即 Rabin-Karp 以为自己找到了匹配， 结果却大失所望。请在下面的幻灯片中观看 Rabin-Karp 的实际工作过程。

最后，请完成这个练习：使用改进的 Horner 算法计算字符串的"幻数"， 并跟踪 Rabin-Karp 算法中的一步。