ค้นหาการวางแนวของรูปแบบในเมทริกซ์ใน C++

ในปัญหานี้ เราได้รับเมทริกซ์ที่ประกอบด้วยค่าอักขระที่สร้างรูปแบบ เรายังกำหนดรูปแบบที่จะพบอีกด้วย งานของเราคือค้นหาการวางแนว (แนวนอนหรือแนวตั้ง) ของรูปแบบในเมทริกซ์

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

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

ผลลัพธ์

vertical

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาง่ายๆ คือการค้นหารูปแบบขนาด M ในแถว N ทั้งหมดของเมทริกซ์ วิธีแก้ปัญหานี้ใช้ได้ แต่วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าคือการใช้อัลกอริทึมการจับคู่รูปแบบ KML สำหรับแถวและคอลัมน์ทั้งหมดของเมทริกซ์

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

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

ผลลัพธ์

The orientation of the pattern in matrix is vertical