Codeforces 335B Palindrome

問題

長さnの英小文字からなる文字列が与えられる。
この文字列の（必ずしも連続しない）部分文字列で、長さがちょうど100の回文は存在するか。
存在するならそれをどれか一つ、存在しないなら、部分文字列の回文のうち最も長いものをどれか一つ出力せよ。

制約条件

n≦5*10^4

方針

O(n^2 * |アルファベット|)で部分文字列の回文の最長の長さを求めるには、
dp[l][r] := 最大の長さ
というDPをすればいい。

が、これだと間に合わない。
長さが100以下という条件を使いたい。
dp[l][長さ] ;= rの最小値
のように少し変形したDPをすれば、O(n * 長さ * |アルファベット|）で、
長さ100以下の回文の長さの最大値が求まる。

求まったら経路復元すればいい。

ソースコード

const int MX = 50010;
int n;
string in;
int dp[102][MX], r[MX][26], l[MX][26];
int prev[102][MX];

int main(){
	cin >> in;
	n = in.size();
	
	memset(dp, -1, sizeof(dp));
	rep(i, 26){
		r[n][i] = n;
		l[0][i] = -1;
	}
	for(int i = n - 1; i >= 0; i--) rep(j, 26){
		if(in[i] - 'a' == j) r[i][j] = i;
		else r[i][j] = r[i + 1][j];
	}
	rep(i, n) rep(j, 26){
		if(in[i] - 'a' == j) l[i + 1][j] = i;
		else l[i + 1][j] = l[i][j];
	}
	
	rep(i, n){
		dp[1][i] = i;
		if(i > 0 && l[i][in[i] - 'a'] >= 0) dp[2][i] = l[i][in[i] - 'a'];
	}
	rep(i, 100) rep(j, n) if(dp[i][j] >= 0){
		rep(k, 26){
			if(r[j + 1][k] >= n || l[dp[i][j]][k] < 0) continue;
			if(dp[i + 2][r[j + 1][k]] >= l[dp[i][j]][k]) continue;
			
			dp[i + 2][r[j + 1][k]] = l[dp[i][j]][k];
			prev[i + 2][r[j + 1][k]] = j;
		}
	}
	
	int mx = 0, mxj;
	rep(i, 101) rep(j, n) if(dp[i][j] >= 0){
		if(mx < i){
			mx = i;
			mxj = j;
		}
	}
	string ans, s;
	int a = mx, b = mxj;
	rep(i, (mx + 1) / 2){
		s += in[dp[a][b]];
		b = prev[a][b];
		a -= 2;
	}
	ans = s;
	reverse(all(s));
	if(mx % 2) s = s.substr(1);
	ans += s;
	
	cout << ans << endl;
	
	return 0;
}