首页 > 代码库 > HDU 3901 Wildcard
HDU 3901 Wildcard
题目：Wildcard
链接：http://acm.hdu.edu.cn/showproblem.php?pid=3901
题意：给一个原串（只含小写字母）和一个模式串（含小写字母、？、* ，*号可替换为0到无穷个任意字母，？可替换为一个任意字母），问两个字符串是否匹配。
思路：
这是经典题吧。。。
AC自动机。（网上大多代码是错的，用普通kmp是不行的，不知道修改过后可不可以）。
HDU已经加强数据了，可我前一个代码abcd ？显示是YES居然还过了，看来数据还是有点弱啊。
*号的处理是很容易的，只需要把模式串以*号为分界分解开来，然后除了最后一段，其他尽量匹配靠前的原串子串就差不多了，比如ab*cd*ef*gh，那么原串必须以ab开头、gh结尾、然后找到最前的cd、再找到ef，如果互相不重叠就OK。
比较难的是？的处理了，*分解开模式串分别处理。现在，根据？分解，将分解后的字符串（不含？号了）构建AC自动机。
比如串A：abcd?abc?cd?abcd，构建AC自动机，然后在结束点记录他在串A中的位置。
红色为根，黄色为每一个结束点，这里的fail指针与普通AC自动机相同
现在我们创建一个数组cnt，对应原串的每一位，让原串在自动机上跑，如果遇到黄点cnt[当前位置-记录的值+1]++，比如遇到abcd，那说明原串当前位置前四位一定是abcd，满足这一段，而如果有某一个cnt值等于4，就说明他满足了所有段，那么他可以作为串A匹配的起点，a b c d _ a b c _ c d _ a b c d，只有上面这种情况才会使第一个a的cnt值为4，而cnt等于4，当前位就是该次匹配满足的最前位置了。
上一段理解后，题目就可以得解了，注意细节就是了。
AC代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<set> 6 #include<map> 7 #include<list> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 #include<string> 12 #include<iostream> 13 #include<algorithm> 14 using namespace std; 15 #define lson rt<<1 16 #define rson rt<<1|1 17 #define N 100010 18 #define M 26 19 #define Mod 1000000007 20 #define LL long long 21 #define INF 0x7fffffff 22 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++) 23 #define For(i,f_start,f_end) for(int i=f_start;i<f_end;i++) 24 #define REP(i,f_end,f_start) for(int i=f_end;i>=f_start;i--) 25 #define Rep(i,f_end,f_start) for(int i=f_end;i>f_start;i--) 26 #define MT(x,i) memset(x,i,sizeof(x)) 27 #define gcd(x,y) __gcd(x,y) 28 const double PI = acos(-1); 29 30 struct Node 31 { 32 vector<int> d; 33 int fail; 34 int next[M]; 35 }v[N]; 36 int vNum; 37 38 void Init() 39 { 40 v[0].fail = -1; 41 FOR(i,0,25){ 42 v[0].next[i]=-1; 43 } 44 vNum=1; 45 } 46 47 int create() 48 { 49 v[vNum].d.clear(); 50 v[vNum].fail=-1; 51 for(int i=0;i<M;i++) v[vNum].next[i]=-1; 52 return vNum++; 53 } 54 55 int getPos(char c) 56 { 57 return c-‘a‘; 58 } 59 60 int add(char *s) 61 { 62 int i,ret=0,p=0; 63 for(i=0;s[i];i++){ 64 if(s[i]==‘?‘){ 65 if(p!=0){ 66 ret++; 67 v[p].d.push_back(i); 68 p=0; 69 } 70 } 71 int pos = getPos(s[i]); 72 if(v[p].next[pos]==-1) v[p].next[pos]=create(); 73 p = v[p].next[pos]; 74 } 75 if(p!=0){ 76 ret++; 77 v[p].d.push_back(i); 78 } 79 return ret; 80 } 81 82 queue<int> q; 83 void makeFail() 84 { 85 q.push(0); 86 while(q.size()) 87 { 88 int p=q.front(); 89 q.pop(); 90 for(int i=0;i<M;i++) 91 { 92 if(v[p].next[i]!=-1) 93 { 94 int t=v[p].fail; 95 while(1) 96 { 97 if(t == -1) // p 已经是根了 98 { 99 v[v[p].next[i] ].fail = 0;100 break;101 }102 else if(v[t].next[i] != -1)103 {104 v[v[p].next[i] ].fail = v[t].next[i];105 break;106 }107 else t=v[t].fail;108 }109 if(t!=-1){110 for(int j=0;j<v[t].d.size();j++){111 v[p].d.push_back(v[t].d[j]);112 }113 }114 q.push(v[p].next[i]);115 }116 }117 }118 }119 120 int cnt[N];121 int match(char *s,char *s1)122 {123 Init();124 int duan = add(s1);125 if(duan==0) return 0;126 127 makeFail();128 129 //printf("%s %s %d\n",s,s1,duan);130 131 memset(cnt,0,sizeof(cnt));132 int i,p=0;133 for(i=0;s[i];i++){134 int pos = getPos(s[i]);135 if(p==-1){136 p=0;137 continue;138 }139 if(v[p].next[pos]==-1){140 p = v[p].fail;141 i--;142 continue;143 }144 p = v[p].next[pos];145 for(int j=0;j<v[p].d.size();j++){146 cnt[i-v[p].d[j]+1]++;147 if(cnt[i-v[p].d[j]+1]==duan) return i-v[p].d[j]+1;148 }149 }150 return -1;151 }152 153 char s[N],s1[N],s2[N];154 bool solve(char *s,char *s1)155 {156 int ls=strlen(s),ps=0;157 int i,len=0,flag=0;158 for(i=0;s1[i];i++){159 if(s1[i]==‘*‘){160 if(len!=0){161 s2[len]=0;162 int qi = match(s+ps,s2);163 if(qi==-1) return false;164 if(flag==0 && qi!=0) return false;165 ps += qi + len;166 if(ps>ls) return false;167 len = 0;168 }169 flag=1;170 }171 else s2[len++]=s1[i];172 }173 if(len!=0){174 len--;175 for(i=ls-1;i>=ps && len>=0;i--){176 if(s2[len]!=‘?‘ && s2[len]!=s[i]) return false;177 len--;178 }179 if(i>=ps && flag==0 || len>=0) return false;180 }181 return true;182 }183 184 int main()185 {186 while(scanf("%s%s",s,s1)!=EOF)187 {188 printf("%s\n",solve(s,s1)?"YES":"NO");189 }190 return 0;191 }
HDU 3901 Wildcard
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。