在计算机（软件）技术中，通配符可用于代替字符。 通常地，星号“*”匹配0个或以上的字符，问号“?”匹配1个字符。（wiki百科）

今天做Leetcode上的一道题时不会做，网上查到了这么一种做法，当年打比赛的时候都没有碰到过。。。。

Leetcode Wildcard Matching

递归做法TLE

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        char cs = *s;
        char cp = *p;
        if(cp == ‘\0‘) {
            return cs == cp;
        } else if (cp == ‘?‘) {
            if (cs == ‘\0‘) return false;
            return isMatch(s + 1,p + 1);
        } else if (cp == ‘*‘) {
            const char *st = s;
            while(cp == ‘*‘){
                p++;
                cp = *p;
            }
            for(; *st != ‘\0‘; ++st) {
                if (isMatch(st, p)) return true;
            }
            return isMatch(st,p);
        } else if (cp != cs)
            return false;
        return isMatch(s + 1,p + 1);
    }
};

class Solution {
public:
    bool isMatch(const char *s, const char *p) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
           
        const char* star=NULL;  
        const char* ss=s;   
        while (*s){  
            if ((*p==‘?‘)||(*p==*s)){s++;p++;continue;}  
            if (*p==‘*‘){star=p++; ss=s;continue;}  //star可以更新，使用贪心法
            if (star){ p = star+1; s=++ss;continue;}
            return false;  
        }  
        while (*p==‘*‘){p++;}  
        return !*p;  
    }  

};

HDU 3901
关于AC自动机通配符匹配的相关知识请看点击打开链接

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005
#define B 26

int tree[N][B],size;
vector<int> key[N];
int cnt[N],tcnt;
void build(char str[]){
    size=tcnt=0;
    memset(tree[0],0,sizeof(tree[0]));
    key[0].clear();

    int node=0;
    for(int i=0;!i||str[i-1];i++){
        if(str[i]==‘?‘||str[i]==0){
            if(node){
                key[node].push_back(i-1);
                node=0; tcnt++;
            }
            continue;
        }else{
            int c=str[i]-‘a‘;
            if(!tree[node][c]){
                tree[node][c]=++size;
                memset(tree[size],0,sizeof(tree[size]));
                key[size].clear();
            }
            node=tree[node][c];
        }
    }
}

int que[N];
int fail[N];
void getfail(){
    int *s=que,*e=que;
    for(int i=0;i<B;i++){
        if(tree[0][i]){
            fail[tree[0][i]]=0;
            *e++=tree[0][i];
        }
    }
    while(s!=e){
        int p=*s++;
        for(int i=0;i<B;i++){
            if(tree[p][i]){
                int v=tree[p][i];
                *e++=v;
                fail[v]=tree[fail[p]][i];
                if(key[fail[v]].size()){
                    key[v].insert(key[v].end(),
                            key[fail[v]].begin(),key[fail[v]].end());
                }
            }else{
                tree[p][i]=tree[fail[p]][i];
            }
        }
    }
}

int find(char str[]){
    if(tcnt==0) return 0;
    int node=0;
    for(int i=0;str[i];i++){
        node=tree[node][str[i]-‘a‘];
        cnt[i] = 0; 
        for(int j=0;j<key[node].size();j++){
            if(i>=key[node][j]){
                cnt[i-key[node][j]]++;
                if(cnt[i-key[node][j]]==tcnt) return i-key[node][j];
            }
        }
    }
    return -1;
}

char tmp[N];
char src[N];
char wild[N];
bool match(int ls, int lp){
    int tl=0;
    for(int i=0;i<lp;i++) if(wild[i]!=‘*‘) tl++; 
    if(tl>ls) return false;

    int s=-1;
    for(int i=0;i==0||src[i-1];i++){   //如果最左不是*需要从头开始匹配到第一个*
        if((src[i]!=0&&wild[i]==‘?‘)||src[i]==wild[i]) continue;
        if(wild[i]==‘*‘) s=i+1;
        else return false;
        break; 
    }
    if(s==-1) return true; 
    
    for(int i=ls-1,j=lp-1;;i--,j--){   //如果最右不是*需要从结尾开始倒着匹配到倒数第一个*
        if(i==-1&&j==-1) break;
        if(i==-1){
            if(wild[j]!=‘*‘) return false; 
            break;
        }
        if(j==-1) return false; 
        if(src[i]==wild[j]||wild[j]==‘?‘){
            src[ls=i] = wild[j] = 0;
        } else if(wild[j]==‘*‘) break;
        else return false;
    }

    int ts=s-1;
    for(int i=1;i<lp-tl;i++){       //剩下的部分为*......*将其中每个**中间部分用AC自动机匹配即可
        if(wild[s]==‘*‘){s++;continue;}
        int len = 0;
        for(;wild[s]!=‘*‘&&wild[s];s++){
            tmp[len]=wild[s];
            tmp[++len]=0;
        }
        s++;
        build(tmp);
        getfail();    //这两步构造AC自动机
        int pos=find(src+ts);   //寻找最左边匹配位置
        if(pos==-1) return false; 
        else{
            ts+=pos+len;
            if(ts>ls) return false; 
        }
    }
    return true; 
} 

int main(){
    while(~scanf("%s", src)){
        scanf("%s", wild);
        puts(match(strlen(src), strlen(wild))?"YES":"NO"); 
    }
}

参考文章

http://www.cnblogs.com/ambition/archive/2011/08/26/wildcard.html

http://www.cnblogs.com/zcwwzdjn/archive/2012/03/10/2389514.html

AC自动机通配符匹配