ワイルドカードというものがあり、*は任意の文字列 ?は任意の一文字にマッチします。たとえばc*tにはcatやcourtがマッチします。形式言語学で言うと、ワイルドカードは正規表現の一種なのでオートマトンの応用で判定できます。たとえばc*tとcatを考えます。

   c * t   ->  c * t  ->  c * t  ->  c * t

  ^          c    ^      a     ^ ^   t     ^ ^ ^

まずスタート位置にコマ(^)を置きます。文字が一致すれば次に進みます。パターンが?の時にはどの文字にもマッチします。パターンが*の時には、元の位置にも残して次の位置にもコマを進めます。このようにして、最後にゴール地点にコマがあればマッチしたことになります。

 

 

以前に考えたコードに間違いがあったようで、複数のコマがある情況では処理が衝突することがあるので、いったん新しい所に作成して書き戻すようにしました。またc*tにctをマッチさせるにはイプシロン遷移という処理が必要です。とりあえず、動いています。

 

BOOL IsWild()

{

    int lenP = lstrlen(pat);

    int lenS = lstrlen(str);

    for (int i = 0; i < 100; i++)

        bWild[i] = FALSE;

    bWild[0] = TRUE;

    for (int i = 0; i < lenS; i++)

    {

        for (int j = 0; j <= lenP; j++)

            bNext[j] = FALSE;

        int c = str[i];

        for (int j = 0; j < lenP; j++)

        {

            int d = pat[j];

            if (bWild[j])

            {

                switch (d)

                {

                case '*':

                    bNext[j] = TRUE;

                    bNext[j + 1] = TRUE;

                    break;

                case '?':

                    bNext[j + 1] = TRUE;

                    break;

                default:

                    if (c == d)

                        bNext[j + 1] = TRUE;

                    break;

                }

            }

        }

        for (int j = 0; j <= lenP; j++)

            bWild[j] = bNext[j];

        for (int j = lenP; j > 0; j--)

        {

            if (bWild[j - 1] && pat[j - 1] == '*')

                bWild[j] = TRUE;

        }

    }

    return bWild[lenP];

}