와일드카드 패턴 일치

이 문제에 대해 하나의 기본 문자열과 다른 와일드카드 패턴이 제공됩니다. 이 알고리즘에서는 와일드카드 패턴이 본문과 일치하는지 여부를 확인합니다.

와일드카드 패턴에는 문자나 '*' 또는 '?' 기호가 포함될 수 있습니다. '?'는 단일 문자를 일치시키는 데 사용하고 '*'는 공백을 포함한 문자의 시퀀스를 일치시키는 데 사용합니다.

캐릭터가 '*'일 때 :별 캐릭터는 무시하고 패턴에서 다음 캐릭터를 확인하기 위해 이동할 수 있습니다.

다음 문자가 '?'인 경우 텍스트에서 현재 문자만 무시하고 패턴과 텍스트에서 다음 문자를 확인할 수 있습니다.

패턴 문자가 '*', '?'가 아닌 경우 패턴과 텍스트의 현재 문자가 일치하면 앞으로만 이동합니다.

입력 및 출력

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.