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; }