UVa-10453 : Make Palindrome

問題概要

長さL(<1000)の文字列が与えられる。いくつか文字を任意の場所に追加して回文になるようにしたい。最小いくつ追加する必要があるかもとめる問題。また実際に回文を出力する。

解法

strとrev(str)のLCSを計算する。LCSに含まれない部分だけを追加すればよい。LCSの復元の方法はちゃんと文字が一致するかどうか確かめないと駄目。

acceptされたコード

計算量O(L^2)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_L = 1000;

int dp[MAX_L + 1][MAX_L + 1];
bool match[MAX_L + 1];

char str[MAX_L + 1], rev[MAX_L + 1], ans[MAX_L + 1];

bool init(){
	return gets(str);
}

void solve(){
	const int L = strlen(str);
	for(int i=0; i<L; i++){
		rev[L - i - 1] = str[i];
	}
	rev[L] = '\0';

	for(int i=0; i<L; i++){
		for(int j=0; j<L; j++){
			if(str[i] == rev[j]){
				dp[i+1][j+1] = dp[i][j] + 1;
			}
			else{
				dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
			}
		}
	}

	const int N = dp[L][L];
	{
		memset(match, false, sizeof(match));
		int p = L, q = L;
		while(dp[p][q] > 0){
			if(str[p-1] == rev[q-1] && dp[p-1][q-1] + 1 == dp[p][q]){
				p--;
				q--;
				match[p] = true;
			}
			else if( dp[p][q-1] == dp[p][q] ){
				q--;
			}
			else if( dp[p-1][q] == dp[p][q] ){
				p--;
			}
			else{
				p--;
				q--;
				match[p] = true;
			}
		}
	}

	printf("%d ", L - N);
	{
		int p = 0;
		int s = 0, t = L - 1;
		while(s <= t){
			if(!match[s] && !match[t]){
				ans[p++] = str[s++];
			}
			else if(match[s] && match[t]){
				ans[p++] = str[s];
				s++;
				t--;
			}
			else if(!match[s] && match[t]){
				ans[p++] = str[s++];
			}
			else if(match[s] && !match[t]){
				ans[p++] = str[t--];
			}
		}

		for(int i=0; i<p; i++){
			putchar(ans[i]);
		}
		for(int i=(N%2==0?p-1:p-2); i>=0; i--){
			putchar(ans[i]);
		}
		putchar('\n');
	}

}

int main(){
	while(init()){
		solve();
	}

	return 0;
}