Codeforces #201 Div1. B. Lucky Common Subsequence

pretestが通ったのに、systestはTLEでもなく落としてしまった…。
http://codeforces.com/contest/346/problem/B

問題

3つの文字列S1,S2,Vが与えられる。
S1・S2の共通部分文字列のうちVを含まない最長のものを答えよ。

解法

「Vを含まない」を求める問題なので、先に文字列の遷移表を作る。
あとは最長部分列を求める際、V中何文字目まで来たかを遷移表を使って管理し、Vの終端に到達しないようにDPしていく。
最後に経路復元して終了。

string S0,S1,V;
int SL0,SL1,VL;
struct hogege { int px,py,pz,num,can; };
hogege dpdp[101][101][101];

// state transition table change 'A' if lower
int stt[1024][26];
void CreateSTT(string& pat) {
	int x,y,z,l;
	ZERO(stt);
	l=pat.size();
	FOR(x,l) {
		FOR(y,26) {
			if('A'+y == pat[x]) stt[x][y]=x+1;
			else {
				string pre=pat.substr(0,x)+(char)('A'+y);
				for(z=1;z<=x;z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z;
			}
		}
	}
}

void solve() {
	int f,r,i,j,k,l,x,y,z,tx,ty;
	
	cin>>S0>>S1>>V;
	SL0=S0.size();
	SL1=S1.size();
	VL=V.size();
	CreateSTT(V);
	
	dpdp[0][0][0].can=1;
	FOR(x,SL0) FOR(y,SL1) FOR(z,VL) {
		if(dpdp[x][y][z].can==0) continue;
		
		if(S0[x]==S1[y]) {
			int st=stt[z][S0[x]-'A'];
			dpdp[x+1][y+1][st].can=dpdp[x+1][y][z].can=dpdp[x][y+1][z].can=1;
			//take
			if(dpdp[x+1][y+1][st].num < dpdp[x][y][z].num+1) {
				dpdp[x+1][y+1][st].num = dpdp[x][y][z].num+1;
				dpdp[x+1][y+1][st].px = x;
				dpdp[x+1][y+1][st].py = y;
				dpdp[x+1][y+1][st].pz = z;
				//_P("%d %d %d -> %d %d %d : %d\n",x,y,z,x+1,y+1,st,dpdp[x][y][z].num+1);
			}
		}
		// not take
		dpdp[x+1][y][z].can=dpdp[x][y+1][z].can=dpdp[x+1][y+1][z].can=1;
		if(dpdp[x+1][y][z].num < dpdp[x][y][z].num) dpdp[x+1][y][z] = dpdp[x][y][z];
		if(dpdp[x][y+1][z].num < dpdp[x][y][z].num) dpdp[x][y+1][z] = dpdp[x][y][z];
		if(dpdp[x+1][y+1][z].num < dpdp[x][y][z].num) dpdp[x+1][y+1][z] = dpdp[x][y][z];
	}
	
	int key=SL0;
	FOR(x,SL0+1) FOR(z,VL) if(dpdp[x][SL1][z].num>dpdp[key%128][(key/128)%128][key/(128*128)].num)
		key = z*128*128+SL1*128+x;
	FOR(y,SL1+1) FOR(z,VL) if(dpdp[SL0][y][z].num>dpdp[key%128][(key/128)%128][key/(128*128)].num)
		key = z*128*128+y*128+SL0;
		
	string re;
	while(dpdp[key%128][(key/128)%128][key/(128*128)].num>0) {
		//_P("%d\n",key);
		key = dpdp[key%128][(key/128)%128][key/(128*128)].pz*(128*128)+dpdp[key%128][(key/128)%128][key/(128*128)].py*128
			+dpdp[key%128][(key/128)%128][key/(128*128)].px;
		re = S0[key%128] + re;
	}
	if(re.size()==0) re = "0";
	cout << re << endl;
	
	
	return;
}

まとめ

文字列を含むまたは含まないを判定する問題、遷移表を作る癖をつけないとな。