我正在尝试编写一种算法,用于在给定的子矩阵中查找子矩阵。为了解决这个问题,我编写了以下代码:
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); } } } } } } }}
这段代码可以正常工作,但是我不确定这是问题的确切解决方案还是可以解决。请提供您的专家意见。提前致谢。
该算法对4×4矩阵和2×2子矩阵进行了硬编码。否则,它看起来像蛮力算法。
我会这样表示:
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; } }
如果您想要更有效的方法,建议您将它们压扁,如下所示:
{ 2,3,5,7, 5,8,3,5, 7,6,9,2, 3,8,5,9 }
并在此序列中搜索以下模式:
{ 9,2, _, _, 5, 9}
使用标准的查找子字符串技术,例如Aho- Corasick或Knuth- Morris- Pratt算法。(请注意,您必须跳过一些索引,以避免在序列中间出现新行的情况下误报。)