solution

sEPALIN.cpp

/*
    we either win, or we learn.
*/                  
#include <bits/stdc++.h>   
#define HS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long 
#define pll pair<ll,ll>
#define pb push_back
#define M 100'000'0007
#define lc '\n'
using namespace std;
int main()
{
    HS
    string s;
    while(getline(cin,s))
    {
		ll n=s.length();
		ll dp[n],dp1[n];
		memset(dp,0,sizeof(dp));
		memset(dp1,0,sizeof(dp1));
		ll l=0,r=-1;
		for(ll i=0;i<n;i++)
		{
			ll k=(i>r) ? 1 : min(dp[l+r-i],r-i+1);
			while(i-k>=0 and i+k<n and s[i+k]==s[i-k])
			{
				k++;
			}
			dp[i]=k--;
			if(i+k>r)
			{
				l=i-k;
				r=i+k;
			}
		}
		l=0,r=-1;
		for(ll i=0;i<n;i++)
		{
			ll k=(i>r) ? 0 : min(dp1[l+r-i],r-i);
			while(i-k-1>=0 and i+k<n and s[i+k]==s[i-k-1])
			{
				k++;
			}
			dp1[i]=k--;
			if(i+k>r)
			{
				l=i-k;
				r=i+k;
			}
		}
		ll mask=n-1;
		ll added=n-1;
		ll flag=-1;
		for(ll i=0;i<n;i++)
		{
			if(i+dp[i]==n)
			{
				if(i-(dp[i]-1)<added)
				{
					added=i-(dp[i]-1);
					mask=i;
					flag=1;
				}
			}
		}
		for(ll i=0;i<n;i++)
		{
			if(i+dp1[i]==n)
			{
				if(i-dp1[i]<added)
				{
					added=i-dp1[i];
					mask=i;
					flag=0;
				}
			}
		}
		string s1="";
		if(flag==0)
		{
			for(ll i=0;i<mask-1;i++)
			{
				s1+=s[i];
			}
			cout<<s1<<s[mask]<<s[mask];
			reverse(s1.begin(),s1.end());
			cout<<s1;
			cout<<lc;
		}
		else
		{
			for(ll i=0;i<mask;i++)
			{
				s1+=s[i];
			}
			cout<<s1<<s[mask];
			reverse(s1.begin(),s1.end());
			cout<<s1;
			cout<<lc;
		}
	}
    return 0;
}