java - 查找大矩阵中是否存在小矩阵，时间复杂度为 O(n)

Question

我在面试中被问到一个问题:

Given matrix A and matrix B, I have to write a program to find out whether matrix B exist in matrix 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)。

有什么技术可以在O(n)中搜索小矩阵B是否存在于大矩阵A中？

Answer 1

您可以使用二维滚动哈希。

给定(大)输入矩阵A[N][N] ，以及更小的输入矩阵 M[K][K] ，构造一个新矩阵H1[N][N-K+1]通过散列每个 K每行中的连续元素如下所示:

 H1[i][j] = hash(A[i][j], A[i][j+1], ..., A[i][j+K-1])

如果您的哈希函数被选择为滚动哈希函数(查找)，则它会以线性时间运行，因为您可以构造 H1[i][j+1]来自H1[i][j]在 O(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 的每个元素进行比较，如果它们相等，则几乎肯定有匹配项(您可以逐元素检查)。