从滚动哈希到Rabin-Karp算法：模式匹配的演进

模式匹配是计算机科学中的一项基本任务，用于在文本串中查找指定的模式。在这个过程中，滚动哈希和Rabin-Karp算法发挥了重要的作用。本文将为你揭示这两种算法的原理、应用和优缺点。
一、滚动哈希算法
滚动哈希是一种用于模式匹配的算法，其核心思想是将文本串分成若干个固定长度的窗口，并对每个窗口计算哈希值。通过比较窗口之间的哈希值，可以快速定位到目标模式的位置。
以下是滚动哈希算法的步骤：

1. 定义窗口大小：选择一个合适的窗口大小，通常为固定长度或可变长度。
2. 计算哈希值：对每个窗口计算哈希值，可以使用常见的哈希函数，如MD5或SHA-1。
3. 比较哈希值：在计算完所有窗口的哈希值后，比较相邻窗口的哈希值。如果两个窗口的哈希值相等，则说明目标模式可能存在于这两个窗口之间。
4. 验证匹配：通过逐个字符比较相邻窗口之间的文本，验证是否存在目标模式。
   以下是一个简单的Python示例，演示了如何使用滚动哈希算法进行模式匹配：

   def rolling_hash(text, pattern):
   window_size = len(pattern)
   text_hash = 0
   pattern_hash = 0
   prefix_hash = 0
   for i in range(window_size):
   text_hash ^= ord(text[i]) << (8 * (window_size - i - 1))
   pattern_hash ^= ord(pattern[i]) << (8 * (window_size - i - 1))
   prefix_hash ^= text_hash << (8 * i)
   prefix_hash ^= text_hash >> (8 * (window_size - 1))
   result = []
   for i in range(len(text) - window_size + 1):
   if prefix_hash == text_hash:
   result.append(i)
   text_hash = (text_hash << 8) ^ prefix_hash ^ ord(text[i + window_size]) << (8 * (window_size - 1))
   return result

   这个示例中，我们定义了一个rolling_hash函数，它接受一个文本字符串和一个模式字符串作为输入，并返回模式在文本中出现的所有位置的索引列表。在函数内部，我们使用滚动哈希的思想计算文本和模式的哈希值，并根据哈希值确定匹配的位置。最后，我们通过逐个字符比较相邻窗口之间的文本来验证匹配是否正确。
   二、Rabin-Karp算法
   Rabin-Karp算法是一种基于哈希函数的字符串匹配算法，它在模式匹配中具有高效性和准确性。该算法通过构建一个包含模式中所有字符的哈希表来快速定位模式在文本中的位置。与滚动哈希不同的是，Rabin-Karp算法使用多个哈希表来提高匹配的准确性。
   以下是Rabin-Karp算法的步骤：
5. 构建哈希表：根据模式字符串的每个字符构建一个哈希表。哈希表的键是字符本身，值是字符的幂次和模某个大质数的结果。这样可以确保不同的字符具有不同的哈希值，相同的字符具有相同的哈希值。
6. 计算文本的哈希值：对文本串中的每个字符计算哈希值，并使用这些哈希值构建一个新的哈希表。这个新哈希表的键是文本中的子串，值是子串对应的文本位置列表。
7. 查找匹配：通过查找新哈希表中是否存在与模式字符串对应的键，可以快速找到模式在文本中的位置。如果找到了与模式字符串对应的键，则可以通过验证来确保匹配是准确的。
8. 验证匹配：通过逐个字符比较找到的模式与实际模式的文本，验证匹配是否正确。如果验证通过，则返回匹配的位置；否则，继续查找下一个匹配位置。
   ```python
   def rabin_karp(text, pattern):
   pattern_hash = 0
   p = len(pattern) - 1 # 最后一个字符的ASCII码值
   q = 256 # ASCII码值的模数（256个字符）