java - 在另一个矩阵中快速找到矩阵

Question

如果有一个 m 阶矩阵 A[][] 和另一个 n 阶矩阵 B[][] 使得 (m>n) 你必须在矩阵 A[][ 中找到矩阵 B[][] 的出现]。

A[5][5]=
 1,2,3,4,5
 5,4,1,9,7 
 2,1,7,3,4
 6,4,8,2,7
 0,2,4,5,8

B[3][3]=
 1,9,7
 7,3,4
 8,2,7

这个矩阵 B 存在于 A 中。我可以通过滑动窗口算法 T O(p^2*n^2) 其中 p = m-n+1 来做到这一点。但我想以最小的时间复杂度做到这一点。

Answer 1

您可以使用Boyer-Moore 字符串搜索来解决以下问题：

从右到左比较。在第一行中，您将 3 与 7 进行比较。 3 不会出现在 的第一行中B，因此您可以将窗口向右移动 3 个元素。当您再次开始循环时，窗口不适合A' 的第一行的剩余部分。这意味着您可以使用 2 次比较来处理第一行。

在下一行中，您将 1 与 7 进行比较。1 出现在 中B，因此您将窗口移动到刚好使 1 inB超过 1 in 的位置A。

下一个级别将开始与 的右下角进行比较B。这会将 7 与 7 进行比较。由于 7 在 中出现了 3 次B，因此您必须弄清楚如何使用与 Boyer-Moore 类似的规则来有效地移动窗口。

Answer 2

我之前在 stack-overflow 上找到了一个摘要。希望这会给您提供您可以使用的可能算法和方法。提出了一种在二维nxn文本中搜索二维mxm模式的算法。