solution

sNUMOFPAL.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;
    cin>>s;
    ll n=s.length();
    ll dp[n],dp1[n];
    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++;
		}
		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;
		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++;
		}
		dp1[i]=k--;
		if(i+k>r)
		{
			l=i-k;
			r=i-k;
		}
	}
	ll mask=0;
	for(auto i:dp)
	{
		mask+=i;
	}
	for(auto i:dp1)
	{
		mask+=i;
	}
	cout<<mask<<lc;
    return 0;
}