1

假设有两个二维矩阵，A 和 B

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

A 和 B 在维度上是相同的。A[i], B[i] 是 64 位整数

从A的第2列可以看出，矩阵A与B重叠，所以重叠的位置为1，重叠的长度为2；

一个天真的方法如下：

int N = 3; // row
int M = 3; // col
int A[3][3] = {
    {1,2,3},
    {4,5,6},
    {7,8,9}
};
int B[3][3] = {
    {2,3,9},
    {5,6,7},
    {8,9,0}
};
for (int i = 0; i < M;i++) {
    int j = 0;
    for (j = 0; j < M-i; j++) {
        int k = 0;
        for (k = 0; k < N; k++) {
            if (A[k][i + j] != B[k][j]) {
                break;
            }
        }
        if (k < N) break;
    }
    if (j == M - i) return i;
}
4

1 回答 1

2

一种实用的方法是用向量替换矩阵A并包含每列的哈希值。然后你检查向量中的重叠，只有当你找到一个时，你才会检查整个矩阵是否与相同的重叠匹配。Bab

如果您的散列函数不错，那么完整矩阵检查失败的可能性就会很低。

要找到向量重叠，您可以使用类似的策略，检查后缀的a哈希值与前缀的哈希值b，并仅在匹配时检查完整向量，然后检查完​​整矩阵。

为了使其成为优化，您需要能够增量地计算这些前缀和后缀的哈希值，这样您就可以通过在恒定时间内将一个字符添加到前一个后缀的哈希值来获得下一个后缀的哈希值。一个常见的多项式哈希函数使这非常容易。

例如，如果您的哈希函数是：

h = 0;
for item in vec:
    h = h*31 + item;
return h;

然后你有hash(concat(x,y))=hash(x)*(31^y.length) + hash(y)

于 2021-07-30T12:18:43.147 回答