এই সমস্যায়, আমাদের একটি ম্যাট্রিক্স দেওয়া হয়েছে অক্ষর মান নিয়ে গঠিত যা একটি প্যাটার্ন তৈরি করে, আমাদের খুঁজে পাওয়ার জন্য একটি প্যাটার্নও দেওয়া হয়। আমাদের কাজ হল একটি ম্যাট্রিক্সে একটি প্যাটার্নের ওরিয়েন্টেশন (অনুভূমিক বা উল্লম্ব) খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
mat[][] = {
{ r, a, m },
{a, m, c},
{w, f, t}
}
Patern : raw আউটপুট
vertical
সমাধান পদ্ধতি
ম্যাট্রিক্সের সমস্ত N সারিতে M আকারের প্যাটার্ন অনুসন্ধান করে সমস্যার একটি সহজ সমাধান। এই সমাধানটি ঠিক আছে কিন্তু ম্যাট্রিক্সের সমস্ত সারি এবং কলামের জন্য 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
