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

ภาพรวมปัญหา

ได้รับเมทริกซ์ตัวอักษรและรูปแบบ (pattern) ที่ต้องการค้นหา งานคือหาว่ารูปแบบปรากฏในแนว "แนวนอน" (horizontal) หรือ "แนวตั้ง" (vertical)

ตัวอย่าง

อินพุต

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

เอาต์พุต

vertical

วิธีแก้ปัญหา

ใช้ KMP Algorithm (Knuth-Morris-Pratt) ในการค้นหารูปแบบในทุกแถวและทุกคอลัมน์

1. คำนวณ LPS Array (Longest Prefix Suffix) สำหรับ pattern
2. ค้นหา pattern ในแต่ละแถว (แนวนอน)
3. ค้นหา pattern ในแต่ละคอลัมน์ (แนวตั้ง)
4. คืนค่าทิศทางที่เจอ first

โค้ดตัวอย่าง

#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

สรุป

KMP Algorithm ช่วยให้ค้นหา pattern ใน O(N) ต่อแถว/คอลัมน์ แทนที่จะเป็น O(N²) ของการค้นหาแบบธรรมดา