Đối sánh mẫu ký tự đại diện

Đối với vấn đề này, một chuỗi chính và một mẫu ký tự đại diện khác được đưa ra. Trong thuật toán này, nó sẽ kiểm tra xem mẫu ký tự đại diện có khớp với văn bản chính hay không.

Mẫu ký tự đại diện có thể chứa các chữ cái hoặc ký hiệu ‘*’ hoặc ‘?’. Dấu ‘?’ Được sử dụng để khớp với một ký tự đơn lẻ và dấu ‘*’ được sử dụng để khớp với chuỗi ký tự bao gồm cả khoảng trống.

Khi ký tự là ‘*’:Chúng ta có thể bỏ qua ký tự dấu sao và chuyển sang kiểm tra các ký tự tiếp theo trong mẫu.

Khi ký tự tiếp theo là ‘?’, Thì chúng ta chỉ có thể bỏ qua ký tự hiện tại trong văn bản và kiểm tra ký tự tiếp theo trong mẫu và văn bản.

Khi ký tự mẫu không phải là ‘*’ và ‘?’, Thì nếu ký tự hiện tại của mẫu và văn bản khớp với nhau, thì chỉ di chuyển xa hơn.

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

Input:
The main string and the wildcard pattern.
Main String “Algorithm”
Pattern “A*it?m”
Output:
The pattern matched.

Thuật toán

wildcardMatch(text, pattern)

Đầu vào: Văn bản chính và mẫu.

Đầu ra: Đúng khi các mẫu ký tự đại diện khớp với văn bản chính.

Begin
   n := length of the text
   m := length of pattern

   if m = 0, then
      return 0 if n = 0, otherwise return 1
   i := 0, j := 0

   while i < n, do
      if text[i] == pattern[i], then
         increase i by 1
         increase j by 1
      else if j < m and pattern[j] is ? mark, then
         increase i by 1
         increase j by 1
      else if j < m and pattern[j] is * symbol, then
         textPointer := i
         patPointer := j
         increase j by 1
      else if patPointer is already updated, then
         j := patPointer + 1
         i := textPinter + 1
         increase textPointer by 1
      else
         return false
   done

   while j < m and pattern[j] = * symbol, do
      increase j by 1
   done

   if j = m, then
      return true
   return false
End

Ví dụ

#include<iostream>
using namespace std;

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

   if (m == 0)    //when pattern is empty
      return (n == 0);

   int i = 0, j = 0, textPointer = -1, pattPointer = -1;
   while (i < n) {
      if (text[i] == pattern[j]) {    //matching text and pattern characters
         i++;
         j++;
      }else if (j < m && pattern[j] == '?') {    //as ? used for one character
         i++;
         j++;
      }else if (j < m && pattern[j] == '*') {    //as * used for one or more character
         textPointer = i;
         pattPointer = j;
         j++;
      }else if (pattPointer != -1) {
         j = pattPointer + 1;
         i = textPointer + 1;
         textPointer++;
      }else
         return false;
   }

   while (j < m && pattern[j] == '*') {
      j++;     //j will increase when wildcard is *
   }

   if (j == m) {    //check whether pattern is finished or not
      return true;
   }

   return false;
}

int main() {
   string text;
   string 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;
}

Đầu ra

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