如何扩展rabin-karp在nxn字符间寻找mxm模式？
有人能想出一个伪代码吗会对算法的时间复杂度产生影响吗？
最佳答案
一种方法分为三个步骤：
1）对于每条水平线，使用rabin karp rolling hash计算沿该线长度为k的每个连续散列字符段的散列值。
2）对于每一列，使用Rabin-Karp向下滚动散列来获取在步骤（1）中计算的、长度为k的连续文本段的散列值，这些文本段彼此上下紧靠，并计算与文本矩形相对应的组合散列值。
3）像以前一样查找文本的矩形。
在步骤2中，我们从x[0]+x[1]*p+x[1]*p^2+的形式开始…由步骤1产生如果在第二步中使用乘法器P^k，则应该能够在矩形上使用散列函数，这与将矩形重新排列为一行（计算出一个长Rabin Karp散列）的情况相同。
如上所述，您需要足够的存储空间来保存所有矩形输入的散列值。应该很容易将其减少到足够的存储空间，以容纳沿输入运行的一个散列值矩形，但其深度仅与您正在搜索的模式相同。如果你下定决心，多做一点计算，你可能会做得更好。很明显，你可以在搜索之前把区域分割开来，代价是沿着分割的边界重做正方形。
关于algorithm - 二维阵列的Rabin Karp算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29991650/