如何扩展rabin karp在nxn个字符中寻找mxm模式？
谁能提供一个伪代码？并且对算法的时间复杂度有影响吗？
一种方法是分三个步骤：
1）对于每条水平线，使用Rabin-Karp滚动散列来计算散列值，该散列值覆盖沿着该行的长度为k的散列字符的每个连续范围。
2）对于每一列，请使用Rabin-Karp向下滚动该列的哈希值，以获取在步骤（1）中计算的哈希值，以获取长度为k的文本的连续拉伸，该文本的长度紧挨着彼此上下，并计算对应的组合哈希值到文本的矩形。
3）像以前一样查找该矩形文本。
在步骤2中，我们从步骤1产生的形式为X [0] + X [1] * P + X [1] * P ^ 2 + ...的值开始。步骤，您应该能够在矩形上得到一个散列函数，这与将矩形重新排列为单行并计算出一个长Rabin-Karp散列相同。
如上所述，您需要足够的存储空间来保存所有矩形输入的哈希值。应该很容易地将其减少到足够多的存储空间，以容纳沿输入方向运行的散列值的矩形，但其深度与要搜索的模式一样深。如果您全神贯注，并且进行更多的计算，则可能会做得更好。显然，您可以在搜索之前对区域进行划分，但要以重新划分边界为单位的正方形为代价。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句