問題
http://community.topcoder.com/stat?c=problem_statement&pm=8706&rd=11126
解き方
仮の文字列を作る。
＊にあたる共通の部分は？で埋めて、s1とs2について同じ長さの２つの文字列を作る。
各文字について一致していればその文字列は有効になるのでそれが答えになる。
そのような文字列が存在しなければimpossibleとなる。
コード
class TwoStringMasks {
public: string shortestCommon(string s1, string s2) {
for(int l1=0;l1<=200;l1++){
int l2=s1.size()+l1-s2.size();
if(l2<0)continue;
string p1="";
FORE(i,0,s1.size()){
if(s1[i]=='*')FORE(j,0,l1)p1+='?';
else p1+=s1[i];
}
string p2="";
FORE(i,0,s2.size()){
if(s2[i]=='*')FORE(j,0,l2)p2+='?';
else p2+=s2[i];
}
string ans="";
int valid=1;
FORE(i,0,p1.size()){
char ch;
if(p1[i]=='?')ch=p2[i];
else if(p2[i]=='?')ch=p1[i];
else if(p1[i]==p2[i])ch=p1[i];
else{
valid=0;
break;
}
ans+=ch;
}
if(valid)return ans;
}
return "impossible";
}
};
public: string shortestCommon(string s1, string s2) {
for(int l1=0;l1<=200;l1++){
int l2=s1.size()+l1-s2.size();
if(l2<0)continue;
string p1="";
FORE(i,0,s1.size()){
if(s1[i]=='*')FORE(j,0,l1)p1+='?';
else p1+=s1[i];
}
string p2="";
FORE(i,0,s2.size()){
if(s2[i]=='*')FORE(j,0,l2)p2+='?';
else p2+=s2[i];
}
string ans="";
int valid=1;
FORE(i,0,p1.size()){
char ch;
if(p1[i]=='?')ch=p2[i];
else if(p2[i]=='?')ch=p1[i];
else if(p1[i]==p2[i])ch=p1[i];
else{
valid=0;
break;
}
ans+=ch;
}
if(valid)return ans;
}
return "impossible";
}
};