ワイルドカードパターンマッチング

この問題では、1つのメイン文字列と別のワイルドカードパターンが指定されています。このアルゴリズムでは、ワイルドカードパターンが本文と一致しているかどうかを確認します。

ワイルドカードパターンには、文字、「*」または「？」の記号を含めることができます。 「？」は単一の文字に一致するために使用され、「*」は空のスペースを含む文字のシーケンスに一致するために使用されます。

文字が「*」の場合：スター文字を無視して、パターン内の次の文字を確認するために移動できます。

次の文字が「？」の場合、テキスト内の現在の文字のみを無視して、パターンとテキスト内の次の文字を確認できます。

パターン文字が「*」と「？」以外の場合、パターンとテキストの現在の文字が一致している場合は、さらに移動するだけです。

入力と出力

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.