我在采访中被问到一个问题：
给定矩阵
A和矩阵B，我必须编写一个程序来找出矩阵B是否存在于矩阵A中。
问题是我必须在O(n)时间内完成。这是我提出的唯一方法：
public class Matrix {
public static void main(String[] args) {
boolean flag = false;
int a[][] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
int b[][] = {
{11, 12},
{15, 16}};
for (int i = 0; i < a.length - b.length + 1; i++) {
for (int j = 0; j < a[0].length - b[0].length + 1; j++) {
if (a[i][j] == b[0][0]) {
flag = true;
for (int k = 0; k < b.length; k++) {
for (int l = 0; l < b[0].length; l++) {
if (a[i + k][j + l] != b[k][l]) {
flag = false;
break;
}
}
}
if (flag) {
System.out.println("i= " + i + " j= " + j);
return;
}
}
}
}
}
}
我不知道如何将其转换为O(n).
是否有任何技术可以搜索大矩阵B中是否存在小矩阵AO(n)？
您可以使用 2D 滚动哈希。
给定(大的)输入矩阵A[N][N]和较小的输入矩阵M[K][K]，通过散列每行中的每个K连续元素来构造一个新的矩阵H1[N][N-K+1]，如下所示：
H1[i][j] = hash(A[i][j], A[i][j+1], ..., A[i][j+K-1])
如果你的哈希函数被选为滚动哈希函数(查找一下)，它会以线性时间运行，因为你可以在 O(1) 时间内从H1[i][j]构造H1[i][j+1]。
接下来，通过构造一个新的矩阵H2[N-K+1][N-K+1]来对列进行哈希处理：
H2[i][j] = hash(H1[i][j], H1[i+1][j], ..., A[i+K-1][j])
将相同的过程应用于较小的矩阵(生成具有单个元素的矩阵)。
现在，将较小矩阵中的单个哈希值与H2的每个元素进行比较，如果它们相等，则几乎可以肯定匹配(您可以逐元素检查)。
(已编辑)
假设您有一个大小为n x m的矩阵A和一个大小k x l的矩阵B，查找B在A中出现的问题具有简单的朴素时间复杂度O(n m k l)O(1)内存要求。
一般来说，你可以很容易地证明你不能比O(n m)更好，通过考虑需要检查包含矩阵的所有元素的情况k = l = 1，所以O(n m)。这与搜索字符串算法不能(全局)超线性的原因相同。
我假设你对O(N)的要求在O(n m)的要求中翻译得更恰当。如果这是可能的，你可以假设类似的算法可以适应字符串搜索问题，其复杂性O(n)(n输入的大小)，与模式的大小无关k。没有发现这样的算法(甚至可能存在)。出于这个原因，我倾向于相信，如果可能的话，你正在寻找的东西目前超出了人类的知识范围。
相反，基于字符串搜索算法文献，您可以瞄准的是了解复杂性O(n m + k l)。
一种可能的方法是使上述字符串搜索算法之一适应此问题，因此，您应该能够获得类似的时间复杂性和内存要求。
例如，您的算法和@PaulHankin答案都是对 Rabin-Karp 算法适应 2D 情况的描述。 虽然你的版本使用了一个非常糟糕的哈希(每个矩阵的第一个元素)，但如果你要计算一个更高级/更合适的哈希(如建议，但没有提供 - 至少在撰写@PaulHankin答案时)，比如滚动哈希，那么你大部分时间都可以跳过两个最里面的循环， 而滚动哈希将确保您不会向算法添加额外的与输入大小相关的复杂性，这将导致O(n m + k l)时间复杂度(O(k l)来自计算B上的哈希)和O(1)内存要求。
适应其他字符串搜索算法(如高德纳-莫里斯-普拉特(KMP)算法或双向字符串搜索(2WSS)算法)可能需要算法的一些"线性化"(不仅仅是问题公式)，这意味着使用模算术在所有情况下找出正确的偏移量，这可能很乏味，但我看不出为什么这是不可能的，或者会让你失去预期的复杂性。
另一种选择是调整字符串搜索算法以在每个维度中交错工作。但同样，这可能与处理一些"线性化"问题一样困难。
这里的最后一个信息是，绝对有可能超越O(n m k l)并最终O(n m + k l)，但这并不容易。