Ideone.com

fork download

copy

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int tc ; cin >> tc ;
	while(tc--){
		string s ; cin >> s;
		int n = s.size() ;
		vector<vector<int>>dp(n,vector<int>(n,-1)) ;
		function<int(int,int)> calc = [&](int L,int R)->int{
			if(L >= R) return 0 ;
			int &ret = dp[L][R] ;
			if(~ret)
				return ret ;
			if(s[L] == s[R])
				return ret = calc(L + 1,R - 1) ;
			else
				return ret = min(1 + calc(L + 1,R),1 + calc(L,R - 1)) ;
		};
		int cnt = calc(0,n - 1) ;
		int L = 0 , R = n - 1 ;
		string ans ;
		while(L <= R){
			if(s[L] == s[R]) ans.push_back(s[L]) , L ++ , R -- ;
			else{
				if(dp[L][R] != dp[L][R - 1]){
					ans.push_back(s[R]) ;
					R -- ;
				}else{
					ans.push_back(s[L]) , L ++ ;
				}
			}
		}
		string tmp = ans ;
		reverse(begin(ans),end(ans)) ;
		if(cnt + n < 2*ans.size())
			tmp.pop_back() ;
		cout << cnt << endl ;
		cout << tmp << ans << endl ;
	}
	return 0;
}

Success #stdin #stdout 0.03s 5276KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/BfNPSL

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language