SRM 409 DIV1 Easy - OrderedSuperString
問題
http://community.topcoder.com/stat?c=problem_statement&pm=9823&rd=12181
複数の文字列が与えられる。
各文字列を順につなげていく。
ただし、これまでの文字列の後ろ部分と、次につなげる文字列の前部分で一致
しているところがあれば重ねてつなげることができる。
また、毎回つなげる位置は、前につなげた位置もしくはそれより後ろで
なければいけない。
このとき、最後にできた文字列のうち最小のものの長さを求める。
解き方
貪欲法で解くことができる。
毎回最適なつなぎかたを求めていけばよい。
コード
class OrderedSuperString {
public:
string rec(int pos,string s1,string s2){
int cur=0;
while(pos+cur<s1.size() && cur<s2.size()){
if(s1[pos+cur]!=s2[cur])return "";
cur++;
}
if(cur>=s2.size())return s1;
return s1+s2.substr(cur);
}
int getLength(vector<string> words) {
int n=words.size(),pos=0;
string str="";
FORE(i,0,n){
string tmp="";
while(pos<str.size()){
tmp=rec(pos,str,words[i]);
if(!tmp.empty()){
str=tmp;
break;
}
pos++;
}
if(tmp.empty())str+=words[i];
}
return str.size();
}
};
public:
string rec(int pos,string s1,string s2){
int cur=0;
while(pos+cur<s1.size() && cur<s2.size()){
if(s1[pos+cur]!=s2[cur])return "";
cur++;
}
if(cur>=s2.size())return s1;
return s1+s2.substr(cur);
}
int getLength(vector<string> words) {
int n=words.size(),pos=0;
string str="";
FORE(i,0,n){
string tmp="";
while(pos<str.size()){
tmp=rec(pos,str,words[i]);
if(!tmp.empty()){
str=tmp;
break;
}
pos++;
}
if(tmp.empty())str+=words[i];
}
return str.size();
}
};
