查找给定矩阵的子矩阵 [英] Finding sub matrix of a given matrix

问题描述

我正在尝试编写一种算法，用于在给定的子矩阵中查找子矩阵。为了解决这个问题，我编写了以下代码：

i am trying to write an algorithm for finding a sub matrix in a given sub matrix. To solve this problem i had written the following code:

public class SubMatTry {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int a[][] = { { 2, 3, 5, 7 }, { 5, 8, 3, 5 }, { 7, 6, 9, 2 },
            { 3, 8, 5, 9 } };
    int b[][] = { { 9, 2 }, { 5, 9 } };
    int k = 0;
    int l = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            System.out.println("Element of a= " + a[i][j]);
            if (b[k][l] == a[i][j]) {
                System.out.println(b[k][l] + " = " + a[i][j]);
                if (b[k][l + 1] == a[i][j + 1]) {
                    System.out.println(b[k][l + 1] + " = " + a[i][j + 1]);
                    if (b[k + 1][l] == a[i + 1][j]) {
                        System.out.println(b[k + 1][l] + " = "
                                + a[i + 1][j]);
                        if (b[k + 1][l + 1] == a[i + 1][j + 1]) {
                            System.out.println(b[k + 1][l + 1] + " = "
                                    + a[i + 1][j + 1]);
                            System.out.println("Array found at" + i + " ,"
                                    + j);
                            System.exit(0);
                        }
                    }
                }
            }
        }

    }

}}

此代码工作正常，但我不确定这是问题的确切解决方案还是只是一个解决方法。请提供您的专家意见。在此先感谢。

This code is working fine but i am not sure it is the exact solution of the problem or its just a work around. Please provide your expert comments. Thanks in advance.

推荐答案

该算法是针对4× 4矩阵和2× 2子矩阵的硬编码。否则它看起来很好用作蛮力算法。

The algorithm is hard-coded for a 4×4 matrix and a 2×2 submatrix. Otherwise it looks fine as a brute-force algorithm.

我会表达如下：

outerRow:
for (int or = 0; or <= a.length - b.length; or++) {
    outerCol:
    for (int oc = 0; oc <= a[or].length - b[0].length; oc++) {
        for (int ir = 0; ir < b.length; ir++)
            for (int ic = 0; ic < b[ir].length; ic++)
                if (a[or + ir][oc + ic] != b[ir][ic])
                    continue outerCol;
        System.out.println("Submatrix found at row " + or + ", col " + oc);
        break outerRow;
    }
}

---

如果你想要更高效的东西，我建议你把它们压扁，如下：

---

If you want something more efficient, I suggest you flatten them out, like this:

{ 2,3,5,7, 5,8,3,5, 7,6,9,2, 3,8,5,9 }

并在此序列中搜索以下模式：

and search this sequence for the following pattern:

{ 9,2, _, _, 5, 9}

使用标准的find-substring技术，例如 Aho-Corasick 或 Knuth-Morris-Pratt算法。 （请注意，您必须跳过一些索引以避免在序列中间有新行的误报。）

using standard find-substring techniques such as Aho-Corasick or Knuth-Morris-Pratt algorithm. (Note that you would have to skip some indexes to avoid false positives where there's a new row in the middle of the sequence.)

这篇关于查找给定矩阵的子矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！