通配符模式匹配

针对此问题，给出了一个主字符串和另一种通配符模式。在该算法中，它将检查通配符模式是否与主要文本匹配。

通配符模式可以包含字母或“ *”或“？” 符号。'？' 用于匹配单个字符，“ *”用于匹配字符序列，包括空格。

当字符为“ *”时：我们可以忽略星号，然后移动以检查模式中的下一个字符。

当下一个字符为“？”时，我们可以仅忽略文本中的当前字符，并检查模式和文本中的下一个字符。

当图案字符不是'*'和'？'时，则如果图案和文本的当前字符匹配，则仅进一步移动。

输入输出

Input:
The main string and the wildcard pattern.
Main String “Algorithm”
Pattern “A*it?m”
Output:
The 模式匹配。

算法

wildcardMatch(text, pattern)

输入：主要文字和图案。

输出： 当通配符模式与主要文本匹配时为True。

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 << "模式匹配。" << endl;
   else
      cout << "Pattern is not matched" << endl;
}

输出结果

Enter Text: Algorithm
Enter wildcard pattern: A*it?m
模式匹配。