問題
http://community.topcoder.com/stat?c=problem_statement&pm=9943&rd=13508
ある文字列と、接頭辞と接尾辞が与えられる。
ある文字列のサブ文字列について、接頭辞と接尾辞ができるだけマッチするものを求める。
ただし、接頭辞と接尾辞のマッチ数が同じときは接頭辞のマッチ数が大きいものにする。
また、上記も同じであれば文字の昇順のものにする。
解き方
シミュレーション問題なので、いかにシンプルに実装するか。
接頭辞の一致に時間がかかってしまったので、例とＦＯＲを回してみて正しく実装してみるか机上で検証してみるのがやはり大事。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
string P,S;
class TemplateMatching {
public:
int prefixes(string str){
int score=0;
int n1=str.size(),n2=P.size();
FOR(i,0,min(n1,n2)){
string s1=str.substr(0,i+1);
string s2=P.substr(n2-1-i,i+1);
if(s1==s2)score=max(score,i+1);
}
return score;
}
int suffixes(string str){
int score=0;
int n1=str.size(),n2=S.size();
FOR(i,0,min(n1,n2)){
string s1=str.substr(n1-1-i,i+1);
string s2=S.substr(0,i+1);
if(s1==s2)score=max(score,i+1);
}
return score;
}
bool valid(int pre,int suf,int maxprev,int maxsuf,string ret,string str){
if(ret=="")return true;
if(pre+suf>maxprev+maxsuf)return true;
if(pre+suf==maxprev+maxsuf && pre>maxprev)return true;
if(pre+suf==maxprev+maxsuf && pre==maxprev && str<ret)return true;
return false;
}
string bestMatch(string text, string prefix, string suffix) {
string ret="";
int maxprev=0,maxsuf=0;
P=prefix;
S=suffix;
FORE(i,0,text.size()){
string str="";
FORE(j,i,text.size()){
str+=text[j];
int pre=prefixes(str);
int suf=suffixes(str);
if(valid(pre,suf,maxprev,maxsuf,ret,str)){
ret=str;
maxprev=pre;
maxsuf=suf;
}
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
string P,S;
class TemplateMatching {
public:
int prefixes(string str){
int score=0;
int n1=str.size(),n2=P.size();
FOR(i,0,min(n1,n2)){
string s1=str.substr(0,i+1);
string s2=P.substr(n2-1-i,i+1);
if(s1==s2)score=max(score,i+1);
}
return score;
}
int suffixes(string str){
int score=0;
int n1=str.size(),n2=S.size();
FOR(i,0,min(n1,n2)){
string s1=str.substr(n1-1-i,i+1);
string s2=S.substr(0,i+1);
if(s1==s2)score=max(score,i+1);
}
return score;
}
bool valid(int pre,int suf,int maxprev,int maxsuf,string ret,string str){
if(ret=="")return true;
if(pre+suf>maxprev+maxsuf)return true;
if(pre+suf==maxprev+maxsuf && pre>maxprev)return true;
if(pre+suf==maxprev+maxsuf && pre==maxprev && str<ret)return true;
return false;
}
string bestMatch(string text, string prefix, string suffix) {
string ret="";
int maxprev=0,maxsuf=0;
P=prefix;
S=suffix;
FORE(i,0,text.size()){
string str="";
FORE(j,i,text.size()){
str+=text[j];
int pre=prefixes(str);
int suf=suffixes(str);
if(valid(pre,suf,maxprev,maxsuf,ret,str)){
ret=str;
maxprev=pre;
maxsuf=suf;
}
}
}
return ret;
}
};