查找给定矩阵的子矩阵

Question

我想写一个算法来找到给定子矩阵中的子矩阵。为了解决这个问题，我写了下面的代码：

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); 
         } 
        } 
       } 
      } 
     } 

    } 

}} 

此代码工作正常，但我不知道它的问题还是围绕它只是一个工作的精确解。请提供您的专家意见。提前致谢。

Answer 1

该算法是硬编码的矩阵和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 algorithm。 （请注意，您必须跳过一些索引以避免在序列中间出现新行的情况下发生误报）。

Answer 2

首先，我和j不应迭代到3（如果您在[3] [3]你知道它不可能是一个子矩阵的开始，因为基本上你是在矩阵的末尾）。其次，不要使用固定数字，比如4 - 使用a.length来代替（这会给你数组的长度 - 列的数量，而[0] .length会给你第一列的长度 - 有效的行数）。

第三，我会改变的四倍if（原文如此）为双for迭代上K和L，这样的：如果

for (int i = 0; i < a.length - b.length + 1; i++) { 
     for (int j = 0; j < a[0].length - b[0].length + 1; j++) { 
      boolean submatrix = true; // at start we assume we have a submatrix 
      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]) { 
         System.out.println("a[" + (i + k) + "][" + (j + l) + "] = b[" + k + "][" + l + "]"); 
        } else { 
         submatrix = false; // we found inequality, so it's not a submatrix 
        } 
       } 
      } 
      if (submatrix) { 
       System.out.println("Found subatrix at " + i + "," + j + "."); 
      } 
     } 
    } 

（不知道它到底工作，并没有把它通过编译器;））

除此之外，如果你使用java，你应该尝试习惯对象，类和方法（Matrix类与boolean isSubmatrix(Matrix b)方法） - 但对于初学者应该做的。

希望我的回答有帮助。

Answer 3

下面是一个解决方案，我写的基于断描述的策略，通过@aioobe

public static boolean matrixContainsPattern(int[][] data, int[][] pattern) { 
    int[] flatData = flattenMatrix(data); 
    int[] flatPattern = flattenMatrix(pattern); 

    //If the # of rows of data is less than the rows of pattern, we have a problem since we can match at most only a partial amount of the pattern into data 
    if (flatData.length < flatPattern.length) { 
     throw new IllegalArgumentException(); 
    } 

    int dataRowLen = data[0].length; 
    int patternRowLen = pattern[0].length; 
    for (int i = 0; i < flatData.length - flatPattern.length + 1; i++) { 
     //We found a potential match for the pattern 
     if (flatData[i] == flatPattern[0]) { 
      //k can keep track of indexes inside flatData 
      int k = i; 
      //l can keep track of indexes inside flatPattern 
      int l = 0; 
      //dataRowOffset will help us keep track of WHERE we found a match in flatPatterns' imaginary rows 
      int dataRowOffset = (i % dataRowLen); 
      //count to keep track of when we've reached the end of an imaginary row in data 
      int count = 1; 
      boolean patternFound = true; 
      while (k < flatData.length && l < flatPattern.length) { 
       if (flatData[k] != flatPattern[l]) { 
        patternFound = false; 
        break; 
       } 
       //if we reached the end of an imaginary row, we need to skip our pointer k to the next rows offset location 
       //we also need to reset count to the offset, so we can again find the end of this new imaginary row 
       if (count == patternRowLen) { 
        //To get to the position in the next row of where we first found our match, we add to k: the length of whats remaining in our current row, 
        //plus the offset from where we first found in the match in the current row 
        if (dataRowLen == patternRowLen) { 
         k++; 
        } else { 
         k += (dataRowLen - patternRowLen) + dataRowOffset; 
        } 
        count = 1; 
       } else { 
        k++; 
        count++; 
       } 
       l++; 
      } 
      if (patternFound) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

并平整矩阵到一个数组的方法如下：

private static int[] flattenMatrix(int[][] matrix) { 
     if (matrix == null || matrix[0] == null || matrix[0].length < 1) { 
      throw new IllegalArgumentException(); 
     } 
     int[] flattened = new int[matrix.length * matrix[0].length]; 

     int k = 0; 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       flattened[k] = matrix[i][j]; 
       k++; 
      } 
     } 
     return flattened; 
    }