इस समस्या में, हमें एक मैट्रिक्स दिया जाता है जिसमें वर्ण मान होते हैं जो एक पैटर्न बनाते हैं, हमें एक पैटर्न भी दिया जाता है। हमारा काम मैट्रिक्स में पैटर्न के ओरिएंटेशन (क्षैतिज या लंबवत) को ढूंढना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
mat[][] = {
{ r, a, m },
{a, m, c},
{w, f, t}
}
Patern : raw आउटपुट
vertical
समाधान दृष्टिकोण
समस्या का एक सरल समाधान मैट्रिक्स की सभी एन पंक्तियों में एम आकार के पैटर्न की खोज करना है। यह समाधान ठीक है लेकिन समस्या का अधिक प्रभावी समाधान मैट्रिक्स की सभी पंक्तियों और स्तंभों के लिए 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