solution

sMSUBSTR.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
    ll t;
    cin>>t;
    while(t--)
    {
		string s;
		cin>>s;
		ll mx=1;
		map<ll,ll> mp;
		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++;
			}
			//mx=max(mx,k);
			//mp[k]++;
			dp[i]=k;
			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++;
			}
			//mx=max(mx,k);
			//mp[k]++;
			dp1[i]=k;
			k--;
			if(i+k>r)
			{
				l=i-k;
				r=i+k;
			}
		}
		for(auto i:dp)
		{
			mp[2*i-1]++;
			mx=max(mx,2*i-1);
		}
		for(auto i:dp1)
		{
			mp[2*i]++;
			mx=max(mx,2*i);
		}
		cout<<mx<<" "<<mp[mx]<<lc;
	}
    return 0;
}