Solution

slps.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
    // Manchers algorithm
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll dp[n],dp1[n];
    memset(dp,0,sizeof(dp));
    memset(dp1,0,sizeof(dp1));
    ll mask1=1;
    ll l=0,r=-1;
    for(ll i=0;i<n;i++)
    {
		ll k;
		if(i>r)
		{
			k=1;
		}
		else
		{
			k=min(r-i+1,dp[l+r-i]);
		}
		while(i-k>=0 and i+k<n and s[i-k]==s[i+k])
		{
			k++;
		}
		mask1=max(mask1,2*k-1);
		dp[i]=k;
		k-=1;
		if(i+k>r)
		{
			r=i+k;
			l=i-k;
		}
	}
	l=0,r=-1;
	for(ll i=0;i<n;i++)
    {
		ll k;
		if(i>r)
		{
			k=0;
		}
		else
		{
			k=min(r-i,dp1[l+r-i]);
		}
		while(i-k-1>=0 and i+k<n and s[i-k-1]==s[i+k])
		{
			k++;
		}
		mask1=max(mask1,2*k);
		dp1[i]=k;
		k-=1;
		if(i+k>r)
		{
			r=i+k;
			l=i-k;
		}
	}
	ll mask=0;
	for(auto i:dp)
	{
		//cout<<i<<" ";
		mask+=i;
		
	}
	//cout<<lc;
	for(auto i:dp1)
	{
		//cout<<i<<" ";
		mask+=i;
	}
	//cout<<lc;
	cout<<mask1<<lc;
    return 0;
}