TopCoder SRM 615 Div2 Hard MergeStrings

Div2 Hardとはいえ割と簡単な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13095

問題

2つの文字列A,Bを合わせて1つの文字列Cを作る。

問題文中に作り方の正式な定義が書いてあるが、簡単に書くとCの作り方は「AとBのどちらかの先頭文字を取り除いてCの末尾につける」をA,Bが空になるまで続けると考えてよい。

ここで、文字列Sが与えられる。
Sの一部はアルファベットが与えられており、残りは(文字数はわかるが)中身は不明である。
A,Bから生成されるCのうち、Sとマッチするもので辞書順最小のものを答えよ。

解法

Longest Common Substringの要領で、Sの文字列と矛盾しないようにAやBから1文字ずつCの候補を選んでいくだけ。
状態数としてはA,Bの処理済みの文字数のペア分だけあるので、文字列長Lに対しO(L^2)。
加えて文字列処理でO(L)かかるとすると全体でO(L^3)程度。

string memo[52][52];

class MergeStrings {
	string SS,AA,BB;
	public:
	string dodo(int al,int bl) {
		if(memo[al][bl]!="{") return memo[al][bl];
		if(al==AA.size() && bl==BB.size()) return "";
		
		memo[al][bl]="}";
		if(al!=AA.size()) {
			string r=dodo(al+1,bl);
			if(r!="}" && (SS[al+bl]=='?' || SS[al+bl]==AA[al])) memo[al][bl]=min(memo[al][bl],AA[al]+r);
		}
		if(bl!=BB.size()) {
			string r=dodo(al,bl+1);
			if(r!="}" && (SS[al+bl]=='?' || SS[al+bl]==BB[bl])) memo[al][bl]=min(memo[al][bl],BB[bl]+r);
		}
		return memo[al][bl];
	}
	
	string getmin(string S, string A, string B) {
		SS=S,AA=A,BB=B;
		int i,j;
		FOR(i,51) FOR(j,51) memo[i][j]="{";
		
		string res=dodo(0,0);
		if(res=="}") return "";
		return res;
	}
};

まとめ

Longest Common Stringと同じだと気づくとすぐ。