การจับคู่รูปแบบสัญลักษณ์แทน

สำหรับปัญหานี้ จะมีการกำหนดสตริงหลักหนึ่งสตริงและรูปแบบไวด์การ์ดอื่น ในอัลกอริธึมนี้จะตรวจสอบว่ารูปแบบสัญลักษณ์แทนตรงกับข้อความหลักหรือไม่

รูปแบบสัญลักษณ์แทนอาจมีตัวอักษรหรือสัญลักษณ์ '*' หรือ '?' '?' ใช้เพื่อจับคู่อักขระตัวเดียว และ '*' ใช้เพื่อจับคู่ลำดับของอักขระรวมถึงพื้นที่ว่าง

เมื่ออักขระเป็น '*':เราสามารถละเว้นอักขระรูปดาวและย้ายไปตรวจสอบอักขระถัดไปในรูปแบบได้

เมื่ออักขระตัวถัดไปคือ '?' เราจะละเว้นเฉพาะอักขระปัจจุบันในข้อความ และตรวจสอบอักขระตัวถัดไปในรูปแบบและข้อความ

เมื่ออักขระรูปแบบไม่ใช่ '*' และ '?' หากอักขระปัจจุบันของรูปแบบและข้อความตรงกัน ให้ย้ายต่อไปเท่านั้น

อินพุตและเอาต์พุต

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

อัลกอริทึม

wildcardMatch(text, pattern)

ป้อนข้อมูล: ข้อความหลักและรูปแบบ

ผลลัพธ์: เป็นจริงเมื่อรูปแบบสัญลักษณ์แทนตรงกับข้อความหลัก

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

ตัวอย่าง

#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;
}

ผลลัพธ์

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