Нахождение подматрицы данной матрицы

я пытаюсь написать алгоритм для поиска подматрицы в данной подматрице. Чтобы решить эту проблему, я написал следующий код:

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

    }

}}

Этот код работает нормально, но я не уверен, что это точное решение проблемы или просто обходной путь. Пожалуйста, предоставьте свои комментарии экспертов. Заранее спасибо.

 tmikulcek27 мар. 2012 г., 09:38
что-то вроде этого?stackoverflow.com/questions/4358591/...
 Ashwani Kumar29 мар. 2012 г., 07:40
Спасибо tmikulcek за уделенное время на мой вопрос. Предоставленная вами ссылка не решает проблему, на которой я сосредоточен. Но да, это очень помогает приблизиться к решению моей проблемы.

Ответы на вопрос(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;
    }

i и j не должны повторяться до 3 (если вы находитесь на [3] [3], вы знаете, что это не может быть началом подматрицы, потому что в основном вы находитесь в конце матрицы) ,

Во-вторых, не используйте фиксированные числа, такие как 4 - используйте вместо этого a.length (это дает вам длину массива a - количество столбцов, в то время как длина [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) метод) - но для начала это надо сделать.

Надеюсь, мой ответ поможет.

 Ashwani Kumar29 мар. 2012 г., 09:58
если я выполняю ваш код с минутным изменением, которое использует if (a [i] [j] == b [k] [l]) вместо if (a [i] [j] == n [k] [l ]) результат, который я получил: a [0] [0] = b [0] [1] a [1] [0] = b [1] [0]
 r3mbol29 мар. 2012 г., 12:15
ты прав конечно, забыл о двух вещах, извини за неуклюжий ответ;). Я отредактировал код, на этот раз я поставил его через компилятор, и он работает, находя подматрицу в 2,2.
Решение Вопроса

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}

используя стандартные методы поиска подстроки, такие какАхо-Corasick или жеАлгоритм Кнута-Морриса-Пратта, (Обратите внимание, что вам придется пропустить некоторые индексы, чтобы избежать ложных срабатываний, если в середине последовательности есть новая строка.)

 Ashwani Kumar29 мар. 2012 г., 07:35
Из вашего поста я понял, что для решения проблем с подматрицами необходимо сначала преобразовать 2d-массив в 1d-массив, а затем найти заданный шаблон в данном массиве.
 Mr_Hmp06 июн. 2014 г., 20:12
+1 за ответ aioobe
 aioobe29 мар. 2012 г., 08:43
Да. Если вы найдете 9,2, что-то, что-то, 59 в уплощенном массиве, то вы нашли соответствующую подматрицу.
 Adam Bronfin06 сент. 2015 г., 20:48
Это не правильно. Рассмотрим матрицу {[4, 9, 2], [3, 2, 1]} и подматрицу {[9, 2], [2, 1]}. Подматрица присутствует в исходной матрице, но [9, 2, 2, 1] отсутствует в [4, 9, 2, 3, 2, 1].
 aioobe06 сент. 2015 г., 20:54
Правильно, но вам придется искать [9, 2, _, 2, 1], так как у вас есть 3 столбца и вы ищете подматрицу из 2 столбцов.

Ваш ответ на вопрос