首页 > 代码库 > Codeforces Round #425 (Div. 2) B. Petya and Exam（暴力大法好）
Codeforces Round #425 (Div. 2) B. Petya and Exam（暴力大法好）
题目链接：http://codeforces.com/problemset/problem/832/B
题意：给定一些小写字符（定义为好字符，除这些好字符外的其他小写字符都是坏字符）。和字符串S，S里面除了小写字母以外还有？字符，？可以用任何的好字符替代；*字符，*只可以用坏字符串和
空替代，然后给出n个字符串去匹配S字符，问是否能成功。
题解：QAQ，这道题写的我头发又掉了好多。
设拿来匹配S的字符串为T
字符串要匹配，长度要相同吧。*既然这么强大，可以空，那么T的长度最多比S的长度少1；然后不管T长度有多少，只要*符号存在的位置合理，那么就可能匹配。
然后就是匹配了，两个方向 向*位置走在，在这个过程中要保证？的时候T的都是好字符，不是？的时候两者相同。然后就是*代表的那串字符串里面都要是坏字符，
判断一下就可以了。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int num[30]; 7 8 int main(){ 9 ios_base::sync_with_stdio(false);10 int n;11 string S,T,Q;12 cin>>T>>S;13 cin>>n;14 memset(num,0,sizeof(num));15 for(int i=0;i<T.size();i++) num[T[i]-96]=1;16 int Slen=S.size(),flag=0;17 for(int i=0;i<Slen;i++) if(S[i]==‘*‘) flag=1; 18 19 for(int k=0;k<n;k++){20 cin>>Q;21 int idx=1,Qlen=Q.size();22 23 if(Qlen<Slen-flag) {cout<<"NO"<<endl;continue;}24 if(Qlen!=Slen&&!flag) {cout<<"NO"<<endl;continue;}25 26 int s=0,t=1;27 while(S[s]!=‘*‘&&s<Slen&&idx){28 if(S[s]==‘?‘&&num[Q[s]-96]==0) idx=0;29 else if(S[s]!=‘?‘&&S[s]!=Q[s]) idx=0;30 s++; 31 }32 33 while(S[Slen-t]!=‘*‘&&idx&&Slen-t>=0&&Qlen-t>=0){34 if(S[Slen-t]==‘?‘&&num[Q[Qlen-t]-96]==0) idx=0;35 else if(S[Slen-t]!=‘?‘&&S[Slen-t]!=Q[Qlen-t]) idx=0;36 t++;37 }38 39 for(int i=s;i<=Qlen-t&&flag;i++){40 if(num[Q[i]-96]==1)41 idx=0;42 }43 if(idx) cout<<"YES"<<endl;44 else cout<<"NO"<<endl;45 }46 47 return 0;48 }
Codeforces Round #425 (Div. 2) B. Petya and Exam（暴力大法好）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。