Codeforces #244 Div2 D. Match & Catch

最初に思いついた解法に固執して失敗。
http://codeforces.com/contest/427/problem/D

問題

2つの文字列S1,S2が与えられるので、以下の条件を満たす最短文字列があればその長さを答えよ。

• その最短文字列は、両文字列の(連続した)部分文字列と1か所でだけ一致する。

解法

まず、S1内およびS2内の各要素の最長部分prefixを求めておく。

S1[i,i+x]==S2[j,j+x]が答えとなるなら、以下の条件を満たさなければならない。
よって以下を満たす最小のxを求めればよい。

• S1[i,end]とS1[k,end]の最長部分prefixは(i!=kで)x文字未満でなければならない。
• S2[j,end]とS2[k,end]の最長部分prefixは(j!=kで)x文字未満でなければならない。
• S1[i,end]とS2[j,end]の最長部分prefixはx文字以上でなければならない。

それぞれの処理は文字列長Nに対しO(N^2)で行うことができる。

string S[2];
int L[2];

const int AR=5002;
int A0[AR][AR];
int A1[AR][AR];
int A01[AR][AR];
void LCP(string s1,string s2,int arr[AR][AR]) {
	int x,y;
	ZERO(arr);
	for(x=s1.size()-1;x>=0;x--) FOR(y,s2.size()) if(s1[x]==s2[y]) arr[x][y]=arr[x+1][y+1]+1;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S[0];
	cin>>S[1];
	L[0]=S[0].size();
	L[1]=S[1].size();
	
	LCP(S[0],S[0],A0);
	LCP(S[1],S[1],A1);
	LCP(S[0],S[1],A01);
	
	int mi=5001;
	FOR(x,L[1]) {
		A1[x][x]=0;
		FOR(y,L[1]) if(x!=y) A1[x][x]=max(A1[x][x],A1[x][y]);
	}
	
	FOR(x,L[0]) {
		int ma=1;
		FOR(y,L[0]) if(x!=y) ma=max(ma,A0[x][y]+1);
		FOR(y,L[1]) if(A01[x][y]>=ma && A1[y][y]<A01[x][y]) mi=min(mi,max(A1[y][y]+1,ma));
	}
	
	if(mi>5000) _P("-1\n");
	else _P("%d\n",mi);
	
}

まとめ

Longest Common Prefixをライブラリ化しておいた。
Suffix Arrayも準備しておいた方がいいかな…。