Поиск подматрицы в одномерном массиве - C

Question

Добрый день, Мне нужна помощь. Мы получаем домашнее задание для написания программы на C, которая должна генерировать и печатать большую и меньшую матрицу из «X» и «.». И после этого найдите, если меньшая матрица 3x3 находится в большем. Я попытался сделать это на одномерное поле, но моя программа находит матрицу только иногда. Я не могу узнать, где моя ошибка и как ее исправить. Я прочитал некоторые темы на форуме, но ничто из этого не помогло мне. Спасибо за любую помощь.

P.S. Простите меня языковыми ошибками, я не являюсь носителем английского языка.

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

/* Generates matrix of given dimensions */ 
void initMatrix(char *Matrix, int rows, int cols) 
{ 
    for(int i = 0; i < rows; i++) 
    { 
     for(int j = 0; j < cols; j++) 
     { 
     Matrix[i*cols+j]= "X.." [rand() % 3];   // 2/3 that X will be generated 
     } 
    } 
} 

/* Prints given matrix */ 
void printMatrix(char *Matrix, int rows, int cols) 
{ 
    for(int i = 0; i < rows; i++) 
    { 
     for(int j = 0; j < cols; j++) 
      { 
      printf("%c", Matrix[i * cols + j]); 
      } 
     printf("\n"); 
    } 
} 

int main(void) 
{ 
    int rowM1, colM1;        // Dimensions of primary (bigger) matrix 
    int rowM2 = 3, colM2 = 3;      // Dimensions of secondary (smaller) matrix 
    int first, second;          // Position of the begginng of matrix 2 in matrix 1 
    int rel_pos; 
    int i, j, k, l; 
    char *M1 = NULL;        // Pointer to matrix 1 
    char *M2 = NULL;        // Pointer to matrix 2 

    printf("Enter the matrix dimensions separated by a space ([rows] [columns]) : "); 
    if (scanf("%d %d", &rowM1, &colM1) != 2)  // Bad parameters 
    { 
     printf("Wrong parameters."); 
     return 1;         // End program 
    } 

    if (rowM1 < rowM2 || colM1 < colM2) 
    { 
     printf("Matrix 2 can not be found because is bigger than Matrix 1."); 
     return 1; 
    } 

    srand(time(NULL));        // Randomly generates numbers 

    M1 = malloc(rowM1 * colM1 * sizeof(char));  // M1 points to matrix 1 
    M2 = malloc(rowM2 * colM2 * sizeof(char));  // M2 points to matrix 2 

    initMatrix(M1, rowM1, colM1);     // Initializes matrix 1 
    initMatrix(M2, rowM2, colM2);     // Initializes matrix 2 

    printf("\nMatrix 1:\n"); 
    printMatrix(M1, rowM1, colM1);     // Prints matrix 1 
    printf("\nMatrix 2:\n"); 
    printMatrix(M2, rowM2, colM2);     // Prints matrix 2 

    putchar('\n'); 

    for (i = 0; i < rowM1; i++) 
    { 
     for(j = 0; j < colM1; j++){ 
     { 
       for (k = 0; k < rowM2 * colM2; k++) // checking the smaller matrix 
      { 
       if(M1[i*rowM1+j] == M2[k]) 
       { 
        first = i*rowM1; 
        rel_pos = i+1; 
       } 
       if(j % colM2 == 0)     // Matrix 2 has ended on this line, move on next one. 
        rel_pos += colM1 - colM2; 

       if(M1[rel_pos] == M2[j])   // If character are same, keep searching 
        rel_pos++; 

       else        // else this is not the matrix I'm searching for 
        break; 

      } 
       if(k == rowM2*colM2)    // if all k cykle went to the end I found the matrix 
        { 
        printf("Matrix found at [%d][%d]", first, second); 
        return 0; 
        } 
      } 

     } 
       if(i*colM1 > i*colM1-colM2)   // matrix cannot be found 
       printf("Matrix not found"); 
       break; 
     } 

    free(M1);          // frees memory of matrix 1 
    free(M2);          // frees memory of matrix 2 
    return 0; 
} 

Answer 1

Вашему внутреннему цикл for (k = 0; k < rowM2 * colM2; k++) перебирает содержимое маленькой матрицы, а должны сравнивать каждую запись малой матрицы к соответствующему входу в больших матрицах (как определенно в начальной точке, заданной I и J) ,

Сравнение if(M1[i*rowM1+j] == M2[k]), однако, сравнивает все записи малой матрицы с одной и той же записью в большой матрице (индекс массива M1 не зависит от k).

Чтобы это исправить, вам нужно, чтобы сделать четырехмерный петлю

for(y0 = 0; y0 < colM1 - colM2 + 1; y0++) { 
    for(x0 = 0; x0 < rowM1 - rowM2 + 1; x0++) { 
     for(dy = 0; dy < colM2; dy++) { 
      for(dx = 0; dx < rowM2; dx++) { 
       if(M1[(y0 + dy)*rowM1 + (x0 + dx)] == M2[dy*rowM2 + dx]) { 
        ... 
       } 
      } 
     } 
    } 
}