結果

問題 No.2234 palindromer
ユーザー harshith akkapelli
提出日時 2023-03-03 22:33:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,141 bytes
コンパイル時間 2,436 ms
コンパイル使用メモリ 203,336 KB
最終ジャッジ日時 2025-02-11 03:14:42
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long int ll;
using T_=pair<ll,ll>;


void routine(){
	string a;
	cin >> a;
	bool isPali = true;
	int n = a.size();
	for(ll i = 0;i < n/2;i++){
		if(a[i]!=a[n-i-1]) isPali=false;
	}
	if(isPali){
		cout << a << "\n";
		return;
	}
	vector<vector<bool>> dp(n+1,vector<bool>(n+1,false));
	for(ll i = 1;i <= n;i++) dp[i][i]=true;
	for(ll i = 1;i <=n;i++){
		ll j = i-1,k = i+1;
		while(j>=1 and k <= n and a[j-1]==a[k-1]){
			dp[j][k]=dp[j+1][k-1];
			if(dp[j][k]==false) break;
			j--;
			k++;
		}
		j = i-1,k=i;
		if(a[j-1]==a[k-1]) dp[j][k]=true;
		j--;k++;
		while(j>=1 and k <= n and a[j-1]==a[k-1]){
			dp[j][k]=dp[j+1][k-1];
			if(dp[j][k]==false) break;
			j--;
			k++;
		}		
	}
	ll ind = 0;
	for(ll i = 1;i <= n;i++){
		if(dp[i][n]){
			ind =  i;
			break;
		}
	}
	//cout << ind << "\n";
	string ans = "";
	ans += a;
	string b = a;
	a = a.substr(0,ind-1);
	reverse(begin(a),end(a));
	ans += a;
	cout << ans << "\n";
	return;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t = 1;
	while(t--){
		routine();
	}
	return 0;
}
0