传统的模式匹配都是：串T匹配串S，如果存在S的子串S'==T。
　　现在要求的是模糊匹配，串T中含有特殊符'*'和'?'，'*'匹配任意字符串或空串,'?'匹配任意一个字符，如'*Rick'匹配任意以'Rick'结尾的串和'Rick'串，'?ick'匹配任意以'ick'结尾且长度为4的串。
输入：
1、带特殊符的T串
2、一系列测试串S[i]
输出：
如果S[i]匹配T输出.T.，否则输出.F.

１、'?'很好处理，只要在原有的定位函数中加一点点就行：
int index(char *s,char *t,int pos)
{
    int i=pos,j=0,lens=strlen(s),lent=strlen(t);
    while(i    {
        if(s[i]==t[j]||t[j]=='?')//如果t[j]=='?'直接视为匹配成功
        {
            ++i;
            ++j;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(j==lent)return i-lent;
    else return -1;
}

２、'*'的处理有些麻烦，很自然的想法是'*'把整个T串分成若干不含'*'的子串，拿这些子串依次匹配S串。
　　按这样的方法可以把S串分成两类：
Ａ、T=T1*T2*...Tn*，其中Ti为不含'*'的子串，且不为空（T1可为空）。
Ｂ、T=T1*T2*...Tn
　　二者的差别只在于尾部是否有'*'。
　　拿T匹配S，
首先　T1匹配S头部，index(s,t1,0)==0
然后　用循环完成后面的匹配，从前一次匹配后的末尾位置开始向后匹配，如果匹配成功再把末尾位置记录下来。
　　这里只用了最左匹配，为什么就足够了呢？比如实际中的情况T1串可能在S串不止出现一次，为什么只考虑最左一个呢？因为整个匹配过程是从左向右，最左匹配可以保证余下的S子中最长，更有利于后面T子串的匹配成功，试想如果T1最左匹配不成功，靠右一些有可能成功吗？
　　例：T="*is*a*" S="this is a program"
T子串"is"在S中有出现两个位置，匹配的时候只需要考虑最左边那个"is"就行了，因为最左边的"is"匹配成功后，余下的S子串是" is a program"，余下的T子串是"*a"，最左匹配可使余下的S子串最长，匹配的可能最大，最容易匹配的情况已经验证了，就不用再做无用功了。

代码：

/*     模糊匹配       *\
*  ? := d1|d2|...|dn *
*  * := (?)*         *
\*                    */
#include<iostream.h>
#include<string.h>
int index(char *s,char *t,int pos)
{
    int i=pos,j=0,lens=strlen(s),lent=strlen(t);
    while(i<lens&&j<lent)
    {
        if(s[i]==t[j]||t[j]=='?')
        {
            ++i;
            ++j;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(j==lent)return i-lent;
    else return -1;
}
bool match(char *s,char *t)
{
    int i=0,j=0,lens=strlen(s),lent=strlen(t);
    char buf[128];
    int bufp=0;
    while(j<lent&&t[j]!='*')
    {
        buf[bufp]=t[j];
        ++bufp;++j;
    }
    buf[bufp]='\0';
    if(index(s,buf,0)!=0)return false;
    i=bufp;
    while(1)
    {
        while(j<lent&&t[j]=='*')++j;
        if(j==lent)return true;
        bufp=0;
        while(j<lent&&t[j]!='*')
        {
            buf[bufp]=t[j];
            ++bufp;++j;
        }
        buf[bufp]='\0';
        if(j==lent)
        {
            if(index(s,buf,i)!=lens-bufp)return false;
            return true;
        }
        if((i=index(s,buf,i))==-1)return false;
        i+=bufp;
    }
    //return true;
}
void main()
{
    char s[128]="what is this";
    char t[128]="*is*t?is*";
    cout<<match(s,t)<<endl;
}

评论