Searching for a matrix within another matrix in Java

Question

I need to compare two two-dimensional matrices (int[][]) of different sizes, the two being formed by integer values (1 or 0), to verify if there is the smaller matrix within the larger matrix.

Example of larger matrix:

Example of smaller matrix:

I am not able to create the restrictions so that it only goes through a piece of the largest matrix and if one of the values is not equal it already goes through another part of the larger matrix to go comparing with the smaller matrix and so consequently until checking if there is the matrix smaller within the larger matrix.

Answer 1

Basically, first you identify which is the largest matrix and which is the smallest. With this, you use 4 loops for nestled within each other.

• The outer loop runs through a from 0 to alturaMaior - alturaMenor (inclusive).
• The second loop runs through b from 0 to larguraMaior - larguraMenor (inclusive).
• The third loop runs through c from 0 to alturaMenor (exclusive).
• The innermost runs through d from 0 to larguraMenor (exclusive).

The stopping condition of the two inner loops is that they serve to traverse the smaller matrix.

The stopping condition of the two outer loops occurs because they have to traverse only the positions of the larger matrix that may be in the upper left corner of the smaller matrix, and such positions are obtained by subtracting the sizes.

With this the two external loops will go through all possible positions of the larger matrix where the smaller matrix could occur. The two internal loops compare the positions of the smaller matrix with the corresponding one in the larger matrix. This comparison is made by comparing matrizMaior[a + c][b + d] with matrizMenor[c][d]. If they are different, you continue in the second loop, as this means that the smaller matrix is not in that position of the larger one. If the third loop ends without being interrupted, it is because you have tested all positions of the smaller matrix from a position of the larger matrix, and all positions have coincided, and therefore the smaller matrix is within the larger one and you return true. If the first loop ends without being interrupted, it is because you have tested all the positions of the larger matrix and did not find the smaller one from any of them, which proves that the smaller one does not exist within the larger one and you return false.

In the code below, I used int[][], but the same principle works for any other type of die in matrix form (as yours only has zeros and ones, maybe you are using boolean[][]).

import java.util.Objects;

public class ComparaMatrizes {
    public static boolean matrizContem(int[][] matrizMaior, int[][] matrizMenor) {
        Objects.requireNonNull(matrizMaior, "As matrizes não devem ser nulas.");
        Objects.requireNonNull(matrizMenor, "As matrizes não devem ser nulas.");

        // Computa o tamanho das matrizes. 
        int alturaMenor = matrizMenor.length;
        int larguraMenor = alturaMenor == 0 ? 0 : matrizMenor[0].length;
        int alturaMaior = matrizMaior.length;
        int larguraMaior = alturaMaior == 0 ? 0 : matrizMaior[0].length;

        // [Opcional] Rejeita matrizes que tiverem linhas com larguras heterogêneas.
        for (int t = 1; t < alturaMaior; t++) {
            if (matrizMaior[t].length != larguraMaior) throw new IllegalArgumentException("Ambas as matrizes devem ter larguras homogêneas.");
        }
        for (int t = 1; t < alturaMenor; t++) {
            if (matrizMenor[t].length != larguraMenor) throw new IllegalArgumentException("Ambas as matrizes devem ter larguras homogêneas.");
        }

        // Percorre as linhas da matriz maior para procurar a menor.
        for (int a = 0; a <= alturaMaior - alturaMenor; a++) {
            // Percorre as colunas da matriz maior para procurar a menor.
            r: for (int b = 0; b <= larguraMaior - larguraMenor; b++) {

                // Tendo a posição [a][b] da matriz maior como correspondente ao possível canto superior esquerdo da matriz menor,
                // verifica se essa posição contém a matriz menor ao percorrer ambas as matrizes juntas a partir desse ponto.
                // Começa percorrendo as linhas de ambas as matrizes.
                for (int c = 0; c < alturaMenor; c++) {
                    // Percorre as colunas de ambas as matrizes.
                    for (int d = 0; d < larguraMenor; d++) {

                        // Se as coordenadas tiverem valores diferentes, então essa posição da matriz maior não contém a menor.
                        // Dessa forma, se for esse o caso, interrompe o processo de percorrer ambas as matrizes juntas e avança para a
                        // próxima possibilidade na matriz maior.
                        if (matrizMaior[a + c][b + d] != matrizMenor[c][d]) continue r;
                    }
                }

                // Se terminou de percorrer ambas as matrizes (a maior a partir da posição [a][b]) e todas as posições forem iguais, então a matriz menor está dentro da maior.
                return true;
            }
        }

        // Se terminou de percorrer a matriz maior e não encontrou a menor, então é porque a menor não está dentro da maior.
        return false;
    }
}

Note also the matrix validation logic. The program requires both matrices to be non-zero and that all rows in each matrix have the same width (i.e., the line size has to be homogeneous).

Adapt the algorithm to work with matrices of more complex types (e.g., matrices of Strings) it is easy, and in most cases it is only necessary to adapt the condition of the if (for example, use equals with ! instead of !=).

I’ve even used this same algorithm to look for an image inside another image. The adaptations I made were very simple, only changing the access to the indexes of the matrices by accesses to pixels and making the condition of if ignore the transparent pixels of the image sought. With more adaptations in the algorithm, you could do things like color filtering and looking for similar sub-images instead of exactly identical.

And finally, here is a code to test the above method. For all the tests he ends up writing Ok on the console:

public static void main(String[] args) {
    int[][] a = {
        {1, 2, 3, 4, 5},
        {6, 7, 8, 9, 0},
        {5, 4, 3, 2, 1},
        {0, 9, 8, 7, 6}
    };
    int[][] b = {
        {7, 8},
        {4, 3}
    };
    int[][] c = {
        {2, 1},
        {7, 6}
    };
    int[][] d = {
        {4, 3}
    };
    int[][] e = {
        {9}, {2}
    };
    int[][] f = {
        {7, 9}
    };
    int[][] g = {
        {3}, {3}
    };
    int[][] h = {{1, 2, 3, 4, 5, 6}};
    int[][] i = {{1}, {2}, {3}, {4}, {5}, {6}};
    int[][] j = {{}, {}, {}, {}, {}};
    int[][] k = {};
    int[][] m = {{}, {}};

    System.out.println(matrizContem(a, a) ? "Ok 01" : "Erro 01"); // A matriz "a" contém a si mesma: true
    System.out.println(matrizContem(a, b) ? "Ok 02" : "Erro 02"); // A matriz "a" contém "b" em [1][1]: true
    System.out.println(matrizContem(a, c) ? "Ok 03" : "Erro 03"); // A matriz "a" contém "c" em [2][4]: true, este daqui testa o limite da busca na matriz maior.
    System.out.println(matrizContem(a, d) ? "Ok 04" : "Erro 04"); // A matriz "a" contém "d" em [2][1]: true
    System.out.println(matrizContem(a, e) ? "Ok 05" : "Erro 05"); // A matriz "a" contém "e" em [1][3]: true
    System.out.println(matrizContem(b, a) ? "Erro 06" : "Ok 06"); // A matriz menor não pode conter a maior: false
    System.out.println(matrizContem(a, f) ? "Erro 07" : "Ok 07"); // A matriz "a" não contém "f": false
    System.out.println(matrizContem(a, g) ? "Erro 08" : "Ok 08"); // A matriz "a" não contém "g": false
    System.out.println(matrizContem(a, h) ? "Erro 09" : "Ok 09"); // A matriz "a" não contém "h", pois "h" é mais larga que "a": false
    System.out.println(matrizContem(a, i) ? "Erro 10" : "Ok 10"); // A matriz "a" não contém "i", pois "i" é mais alta que "a": false
    System.out.println(matrizContem(a, j) ? "Erro 11" : "Ok 11"); // A matriz "a" não contém "j", pois "j" é mais alta que "a", embora tenha largura zero: false
    System.out.println(matrizContem(a, k) ? "Ok 12" : "Erro 12"); // A matriz "a" contém "k", pois "k" é vazia: true
    System.out.println(matrizContem(a, m) ? "Ok 13" : "Erro 13"); // A matriz "a" contém "m", pois "m", apesar de ter largura zero, tem altura que cabe em "a": true
    System.out.println(matrizContem(k, k) ? "Ok 14" : "Erro 14"); // A matriz vazia "k" contém a si mesma: true

    // Testa as condições de exceções:
    int[][] matrizRuim = {{1, 2, 3}, {4, 5}, {}, {6}, {7, 8, 9, 10}}; // Argh! Linhas de tamanhos diferentes!
    try {
        matrizContem(null, null);
        System.out.println("Erro 15A");
    } catch (NullPointerException esperado) {
        System.out.println("As matrizes não devem ser nulas.".equals(esperado.getMessage()) ? "Ok 15" : "Erro 15B");
    }
    try {
        matrizContem(a, null);
        System.out.println("Erro 16A");
    } catch (NullPointerException esperado) {
        System.out.println("As matrizes não devem ser nulas.".equals(esperado.getMessage()) ? "Ok 16" : "Erro 16B");
    }
    try {
        matrizContem(null, a);
        System.out.println("Erro 17A");
    } catch (NullPointerException esperado) {
        System.out.println("As matrizes não devem ser nulas.".equals(esperado.getMessage()) ? "Ok 17" : "Erro 17B");
    }
    try {
        matrizContem(matrizRuim, matrizRuim);
        System.out.println("Erro 18A");
    } catch (IllegalArgumentException esperado) {
        System.out.println("Ambas as matrizes devem ter larguras homogêneas.".equals(esperado.getMessage()) ? "Ok 18" : "Erro 18B");
    }
    try {
        matrizContem(a, matrizRuim);
        System.out.println("Erro 19A");
    } catch (IllegalArgumentException esperado) {
        System.out.println("Ambas as matrizes devem ter larguras homogêneas.".equals(esperado.getMessage()) ? "Ok 19" : "Erro 19B");
    }
    try {
        matrizContem(matrizRuim, b);
        System.out.println("Erro 20A");
    } catch (IllegalArgumentException esperado) {
        System.out.println("Ambas as matrizes devem ter larguras homogêneas.".equals(esperado.getMessage()) ? "Ok 20" : "Erro 20B");
    }
}

Answer 2

    public static void compareArrays(int[] array1, int[] array2) {
        boolean b = true;
        if (array1 != null && array2 != null){
          if (array1.length != array2.length)
              b = false;
          else
              for (int i = 0; i < array2.length; i++) {
                  if (array2[i] != array1[i]) {
                      b = false;    
                  }                 
            }
        }else{
          b = false;
        }
        System.out.println(b);
    }