ワイルドカードパターンマッチングとは?「*」と「?」の仕組みとC++実装例

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

この問題では、本文(メイン文字列)とワイルドカードパターンの2つが与えられます。アルゴリズムは、与えられたワイルドカードパターンが本文と一致するかどうかを判定します。

ワイルドカードパターンには、通常の英字のほかに「*」や「?」という特殊記号を含めることができます。「?」は任意の1文字に一致し、「*」は空文字列を含む任意の長さの文字列に一致します。

パターン照合の基本ルール

• パターンの文字が「*」の場合: 「*」自体を読み飛ばし、パターンの次の文字から照合を続けます。
• パターンの文字が「?」の場合: 本文の現在の文字のみを読み飛ばし、パターンと本文の両方を1文字ずつ進めて照合します。
• パターンの文字が「*」と「?」以外の場合: パターンと本文の現在の文字が一致したときだけ、先へ進むことができます。

入力と出力

入力:
本文とワイルドカードパターン
本文: "Algorithm"
パターン: "A*it?m"

出力:
パターンが一致しました。

アルゴリズム

wildcardMatch(text, pattern)

入力: 本文とパターン

出力: ワイルドカードパターンが本文と一致すれば真(true)を返します。

begin
   n := テキストの長さ
   m := パターンの長さ

   if m = 0 ならば
      n = 0 のとき 0 を返し、そうでなければ 1 を返す
   i := 0, j := 0

   while i < n である間、繰り返す
      if text[i] == pattern[j] ならば
         i を 1 増やす
         j を 1 増やす
      else if j < m かつ pattern[j] が「?」ならば
         i を 1 増やす
         j を 1 増やす
      else if j < m かつ pattern[j] が「*」ならば
         textPointer := i
         patPointer := j
         j を 1 増やす
      else if patPointer がすでに更新済みならば
         j := patPointer + 1
         i := textPointer + 1
         textPointer を 1 増やす
      else
         false を返す
   done

   while j < m かつ pattern[j] が「*」である間、繰り返す
      j を 1 増やす
   done

   if j = m ならば
      true を返す
   false を返す
end

アルゴリズムのポイント

この手法では、「*」が出現した位置を記録しておくことで、照合に失敗した際に「*」が吸収する文字数を1つずつ増やしながらバックトラック(後退)できます。これにより再帰呼び出しを使わず、2つのポインタだけでマッチングを完結できるのが特徴です。最悪時間計算量は O(n × m)、必要な追加メモリは O(1) で抑えられます。

C++による実装例

#include<iostream>
using namespace std;

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

   if (m == 0)     // パターンが空の場合
      return (n == 0);

   int i = 0, j = 0, textPointer = -1, pattPointer = -1;
   while (i < n) {
      if (text[i] == pattern[j]) {     // 本文とパターンの文字が一致
         i++;
         j++;
      }else if (j < m && pattern[j] == '?') {     // 「?」は任意の1文字に対応
         i++;
         j++;
      }else if (j < m && pattern[j] == '*') {     // 「*」は0文字以上の連続に対応
         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++;     // 残った「*」を読み飛ばす
   }

   if (j == m) {     // パターンを最後まで処理できたか確認
      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.

この例では、パターン「A*it?m」が本文「Algorithm」と正しく一致しています。「A」の直後の「*」が「lgor」の部分に一致し、続く「it」がそのまま一致、「?」が「h」の1文字に対応し、最後の「m」で照合が完了するためです。