32.3-5ワイルドカード付きマッチング(自動機)

機能
このプログラムはワイルドカード*付きのパターン列がテキスト列に存在するか否かを判断し,位置情報を記録していないことを判断することができるが,もちろん記録したいことも可能である.

    :
abccbacbababc
ab*bab*c
    :
1

構想
サンプル入力については、有限自動機を図に示すように、ワイルドカードごとに区切られた文字列を独立したものと見なし、KMPアルゴリズムのcomput_を実行します.suffix_functionプロセスでは、各セクションの先頭のfailが上部の末尾を指し、各セクションの末尾のfailが自分を指します(後続の1つのマッチングに失敗した場合、ワイルドカードは任意の長さの任意の文字列に代わることができるため、KMPアルゴリズムのように前に移動する必要はありません).

#include<stdio.h>
#include<string.h>
#define maxm 1000
typedef struct e{
    char letter;/*  (   )*/
    int end;/*       * ,  end 1*/
    int fail;/*   π  */
}e;
typedef struct MAC{
    int n;/* *     */
    e p[maxm+1];
}MAC;
MAC initmac(void)
{
    char p[maxm];
    scanf("%s",p);
    int i,l,k=0;
    l=strlen(p);
    MAC mac;
    mac.p[0].end=1;/*    , 0*/
    for (i=0;i<l;i++)
        if (p[i]!='*')
        {
            k++;
            mac.p[k].end=0;
            mac.p[k].letter=p[i];
        }
        else
            mac.p[k].end=1;
    mac.n=k;
    return mac;
}
int computfail(MAC *mac)/*        ,           ,     */
{
    int q,i;
    int n=mac->n;
    e *p=mac->p;
    q=0;
    for (i=1;i<=n;i++)
        if (p[i].end)/*     * ,fail    */
        {
            p[i].fail=i;
            q=i;
        }
        else
            if (p[i-1].end)/*           ,   KMP       */
            {
                p[i].fail=i-1;
                q=i-1;
            }
            else/* KMP    ,         π  */
            {
                while ((!p[q].end)&&(p[q+1].letter!=p[i].letter))
                    q=p[q].fail;
                if (p[q+1].letter==p[i].letter)
                    q++;
                p[i].fail=q;
            }
    return 0;
}
int match(MAC *mac,char t[])/* KMP          */
{
    int i,l=strlen(t),q=0;
    int n=mac->n;
    e *p=mac->p;
    for (i=0;i<l;i++)
    {
        while ((!p[q].end)&&(p[q+1].letter!=t[i]))
            q=p[q].fail;
        if (p[q+1].letter==t[i])
            q++;
        if (q==n)
            return 1;/*    KMP        ,        ,               ,            */
    }
    return 0;
}
int main(void)
{
    char t[maxm];
    scanf("%s",t);
    MAC mac;
    mac=initmac();
    computfail(&mac);
    int ans;
    ans=match(&mac,t);
    printf("%d
",ans);
    return 0;
}

欠点は一度しか現れない場所を見つけることです.すべての場所を見つけるには、再帰検索しか知りません.