领手工在家做的网站2019/长沙网站推广服务公司
在计算机（软件）技术中，通配符可用于代替字符。 通常地，星号“*”匹配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);}
};非递归改改AC
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 26int 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