TopCoder SRM 488 Div1 Medium TheBoringStoreDivOne
問題
Johnは文字列Jの看板を、Brusは文字列Bの看板を持っている。
Johnは看板から連続する部分文字列を、空でないかつ重ならないように二つ切り出す。
これらをA,Bとする。
Brusも同様に自分の看板から二つの連続する部分文字列を二つ切り出す。
これらをC,Dとする。
A+CとB+D(ただし+は文字列の結合を表す)が等しくなるような切り出し方のうち、
A+Cが長さ最大(タイの場合は辞書順で最初に来るもの)のA+Cを求めよ。
制約条件
Jの文字数,Bの文字数≦47
方針
A,B全ての切り方を生成する。
AがBの接頭辞またはBがAの接頭辞になっていない場合はA+C=B+Dにならないので捨てる。
AとBの"差"をmapに記録する。
その差を作るようなA,Bが複数ある場合は、長さ最長で、辞書順で最初に来るものを選ぶ。
C,Dの全ての切り方も生成する。
今度は、CがDの接尾辞またはDがCの接尾辞になっている必要がある。
このCとDの"差"もmapに記録する。
この差を作るようなA,Bはmapに記録されているので、
そのようなA,BとC,Dから出来上がる看板がわかる。
この中で長さ最大、辞書順で最初のものを選べばよい。
ソースコード
void ck(string &a,string &b){ if(a.size()<b.size()||a.size()==b.size()&&a>b)a=b; } class TheBoringStoreDivOne { public: string find(string J, string B) { map<string,string> m1,m2; int n=J.size(),m=B.size(); rep(l,n+1)rep(k,l)rep(j,k+1)rep(i,j){ int p=j-i, q=l-k, r=min(p,q); string a=J.substr(i,p), b=J.substr(k,q); if(a.substr(0,r)!=b.substr(0,r))continue; string c=p<q?a:b, d=p<q?b.substr(r):a.substr(r); if(!m1.count(d))m1[d]=c; else ck(m1[d],c); } rep(l,m+1)rep(k,l)rep(j,k+1)rep(i,j){ int p=j-i, q=l-k, r=min(p,q); string a=B.substr(i,p), b=B.substr(k,q); if(a.substr(p-r)!=b.substr(q-r))continue; string c=p<q?a:b, d=p<q?b.substr(0,q-r):a.substr(0,p-r); if(!m2.count(d))m2[d]=c; else ck(m2[d],c); } string ans; fr(i,m1)if(m2.count(i->first)){ string t=i->second+i->first+m2[i->first]; ck(ans,t); } return ans; } };