Wildcard Pattern Matching (การจับคู่รูปแบบวิลด์การ์ด)

กำหนดสตริงหลัก (text) และ wildcard pattern ต้องการตรวจสอบว่า pattern ตรงกับ text หรือไม่

Wildcard Symbols:

• ? - ตรงกับตัวอักษรเดี่ยวใดๆ (exactly 1 character)
• * - ตรงกับลำดับตัวอักษรใดๆ รวมถึง empty string (0 or more characters)

ตัวอย่าง Input และ Output

Input: 
Text: "Algorithm"
Pattern: "A*it?m"

Output: Pattern Matched.
(อธิบาย: A + lgor + it + h + m = Algorithm)

อัลกอริทึม Two Pointers (Greedy with Backtracking)

ฟังก์ชัน wildcardMatch(text, pattern)

แนวคิด: ใช้ตัวชี้ (pointers) และ Backtracking เมื่อเจอ *

1. ตัวชี้ i (text), j (pattern)
2. ตัวชี้จดจำ textPointer, patPointer สำหรับตำแหน่ง * ล่าสุด
3. While i < n:
   • ถ้า text[i] == pattern[j] → i++, j++
   • ถ้า pattern[j] == '?' → i++, j++
   • ถ้า pattern[j] == '*' → จดจำตำแหน่ง (textPointer=i, patPointer=j), j++ (ข้าม *)
   • ถ้าไม่ตรง และมี * ก่อนหน้า → Backtrack: j = patPointer+1, i = ++textPointer
   • มิฉะนั้น → false
4. ข้าม * ที่เหลือท้าย pattern
5. ถ้า j == m → true, มิฉะนั้น false

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

#include <iostream>
#include <string>
using namespace std;

bool wildcardMatch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    if (m == 0) return (n == 0);

    int i = 0, j = 0, textPointer = -1, patPointer = -1;

    while (i < n) {
        if (text[i] == pattern[j]) {
            i++; j++;
        } else if (j < m && pattern[j] == '?') {
            i++; j++;
        } else if (j < m && pattern[j] == '*') {
            textPointer = i;
            patPointer = j;
            j++;
        } else if (patPointer != -1) {
            j = patPointer + 1;
            i = ++textPointer;
        } else {
            return false;
        }
    }

    while (j < m && pattern[j] == '*') j++;
    return (j == m);
}

int main() {
    string text, pattern;
    cout << "Enter Text: "; cin >> text;
    cout << "Enter wildcard pattern: "; cin >> pattern;
    if (wildcardMatch(text, pattern))
        cout << "Pattern Matched." << endl;
    else
        cout << "Pattern is not matched" << endl;
    return 0;
}

Output

Enter Text: Algorithm
Enter wildcard pattern: A*it?m
Pattern Matched.

ความซับซ้อน

• Time: O(n × m) ในกรณีแย่ที่สุด (แต่โดยเฉลี่ยเร็วกว่า)
• Space: O(1)

วิธี DP แบบเต็ม (O(n×m) Space)

ตาราง dp[i][j] = text[0..i-1] match pattern[0..j-1] หรือไม่ - Recurrence ค่อนข้างตรงไปตรงมา แต่ช้ากว่าวิธี Two Pointers