Khớp Mẫu Ký Tự Đặc Biệt (Wildcard Pattern Matching)

Giới thiệu

Cho một chuỗi văn bản và một mẫu chứa ký tự đặc biệt '*' (khớp với chuỗi rỗng hoặc bất kỳ chuỗi nào) và '?' (khớp với đúng một ký tự). Kiểm tra xem mẫu có khớp với văn bản hay không.

Đầu vào và Đầu ra

Đầu vào: Văn bản "Algorithm", Mẫu "A*it?m"
Đầu ra: Mẫu khớp (true).

Thuật toán Duyệt Hai Con Trỏ

Sử dụng hai con trỏ i (văn bản) và j (mẫu), cùng với các biến lưu vị trí khi gặp '*'.

wildcardMatch(text, pattern)
Begin
    n := độ dài text, m := độ dài pattern
    if m = 0 then return (n = 0)
    i := 0, j := 0, textPointer := -1, patPointer := -1
    while i < n do
        if text[i] == pattern[j] then i++; j++
        else if j < m and pattern[j] == '?' then i++; j++
        else if j < m and pattern[j] == '*' then
            textPointer := i; patPointer := j; j++
        else if patPointer != -1 then
            j := patPointer + 1; i := textPointer + 1; textPointer++
        else return false
    done
    while j < m and pattern[j] == '*' do j++ done
    return (j == m)
End

Ví dụ C++

#include <iostream>
using namespace std;

bool wildcardMatch(string text, string pattern) {
    int n = text.size(), 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 + 1; textPointer++;
        }
        else return false;
    }
    while (j < m && pattern[j] == '*') j++;
    return (j == m);
}

int main() {
    string text, pattern;
    cout << "Nhập văn bản: "; cin >> text;
    cout << "Nhập mẫu wildcard: "; cin >> pattern;
    if (wildcardMatch(text, pattern))
        cout << "Mẫu khớp." << endl;
    else
        cout << "Mẫu không khớp." << endl;
    return 0;
}

Kết quả

Nhập văn bản: Algorithm
Nhập mẫu wildcard: A*it?m
Mẫu khớp.