algorithm - 二维数组的 Rabin Karp 算法

Question

如何扩展 rabin karp 以在 nxn 个字符中查找 mxm 模式？

任何人都可以想出一个伪代码吗？并且会对算法的时间复杂度有什么影响吗？

Answer 1

一种方法是分三个步骤：

1) 对于每条水平线，使用 Rabin-Karp 滚动散列来计算散列值，该散列值覆盖沿该线的长度为 k 的散列字符的每个连续延伸。

2) 对于每一列，使用 Rabin-Karp 滚动散列向下列获取在步骤 (1) 中计算的散列值，用于长度为 k 的连续文本段，它们紧邻彼此上方和下方，并计算对应的组合散列值到一个矩形的文本。

3）像以前一样查找那个矩形的文本。

在第 2 步中，我们从第 1 步生成的 X[0] + X[1]*P + X[1]*P^2+... 形式的值开始。如果第二个使用乘数 P^k步骤，你应该能够在一个矩形上得到一个哈希函数，如果你将矩形重新排列为一条线并计算出一个长的 Rabin-Karp 哈希。

如上所述，您需要足够的存储来保存所有矩形输入的哈希值。应该很容易将其减少到足够的存储以容纳沿输入运行的哈希值矩形，但仅与您正在搜索的模式一样深。如果您全神贯注并进行更多计算，可能会做得更好。显然，您可以在搜索之前将区域划分为沿您的划分边界重做正方形的成本。