Tìm hướng của một mẫu trong ma trận trong C ++

Trong bài toán này, chúng ta được đưa ra một ma trận bao gồm các giá trị ký tự tạo thành một mẫu, chúng ta cũng được cung cấp một mẫu cần tìm. Nhiệm vụ của chúng tôi là tìm hướng (ngang hoặc dọc) của một mẫu trong ma trận.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

mat[][] = {
   { r, a, m },
   {a, m, c},
   {w, f, t}
}
Patern : raw

Đầu ra

vertical

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tìm kiếm mẫu có kích thước M trong tất cả N hàng của ma trận. Giải pháp này không sao nhưng giải pháp hiệu quả hơn cho vấn đề là sử dụng thuật toán đối sánh mẫu KML cho tất cả các hàng và cột của ma trận.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include<bits/stdc++.h>
using namespace std;
#define N 3
void calcLpsValues(char *pat, int M, int *lps) {
   int len = 0;
   int i = 1;
   lps[0] = 0;
   while (i < M) {
      if (pat[i] == pat[len]) {
         len++;
         lps[i++] = len;
      } else {
         if (len != 0)
            len = lps[len - 1];
         else
            lps[i++] = 0;
      }
   }
}
int searchPattern(char *pat, char *txt) {
   int M = strlen(pat);
   int *lps = (int *)malloc(sizeof(int)*M);
   int j = 0;
   calcLpsValues(pat, M, lps);
   int i = 0;
   while (i < N) {
      if (pat[j] == txt[i]) {
         j++;
         i++;
      }
      if (j == M)
         return 1;
      else if (i < N && pat[j] != txt[i]) {
         if (j != 0)
            j = lps[j - 1];
         else
            i = i + 1;
      }
   }
   return 0;
}
void findPatternOrientation(char mat[][N], char *pat) {
   char *col = (char*) malloc(N);
   for (int i = 0; i < N; i++) {
      if (searchPattern(pat, mat[i])) {
         cout<<"horizontal";
         return;
      }
      for (int j = 0; j < N; j++)
         col[j] = *(mat[j] + i);
      if (searchPattern(pat, col))
         cout<<"vertical";
   }
}
int main() {
   char mat[N][N] = {{'r', 'a', 'm'},
   {'a', 'm', 'c'},
   {'w', 'f', 't'}};
   char pattern[] = "raw";
   cout<<"The orientation of the pattern in matrix is ";
   findPatternOrientation(mat, pattern);
   return 0;
}

Đầu ra

The orientation of the pattern in matrix is vertical