ম্যাট্রিক্সে প্যাটার্নের অরিয়েন্টেশন খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি ম্যাট্রিক্স দেওয়া আছে যা ক্যারেক্টার মান দিয়ে একটি প্যাটার্ন তৈরি করে, আর আমাদের একটি প্যাটার্ন দিয়ে থাকে যা খুঁজে বের করতে হবে। আমাদের কাজ হল ম্যাট্রিক্সে প্যাটার্নটির অরিয়েন্টেশন (হরিজন্টাল বা ভার্টিক্যাল) খুঁজে বের করা।

উদাহরণ

ইনপুট

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

আউটপুট

vertical

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হল ম্যাট্রিক্সের সব N সংখ্যক সারিতে M আকারের প্যাটার্নটি সার্চ করা। এই সমাধানটি ঠিক আছে, কিন্তু একটি আরও কার্যকর সমাধান হল KMP প্যাটার্ন ম্যাচিং অ্যালগরিদম ব্যবহার করা ম্যাট্রিক্সের সব সারি ও কলামের জন্য।

প্রোগ্রাম উদাহরণ

#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