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