n^2代码如下(当前数据85pts)

#include<iostream>
#include<fstream>
using namespace std;

long ans=0;
long nx[26];
long mn[2000005];
long ml[2000005];

void init(long n,string data)
{
	for(long i=0;i<26;i++)
        nx[i]=-1;
}

void cnt(long n)
{
	for(long i=0;i<n;i++)
		ans+=mn[i];
	return;
}

long getnxt(string data,long l,long r,const char e)
{
//    cout<<r+2<<' '<<e<<' '<<l<<endl;
    for(long i=r;i>=l;i--)
    {
        if(data[i]==e && r-i==ml[r]-ml[i])
            return i;
    }
    return -1;
}

// 01234657
// abbabaab
//     l r*
// 00110012
// 00240028

void solve(long n,string data)
{
    
//    cout<<'0'<<' ';
    if(data[0]==data[1])
        mn[1]=1,ml[1]=2;
//    cout<<mn[1]<<' ';
    for(long i=2;i<n;i++)
    {
        if(data[i]==data[i-1])
        {
            if(i==1)
            {
                mn[i]=1;
                ml[i]=2;
            }
            else
            {
                mn[i]=mn[i-2]+1;
                ml[i]=ml[i-2]+2;
            }
        }
        else
        {
            long nxt=getnxt(data,(i-ml[i-1]-1)>=0?(i-ml[i-1]-1):0,i-1,data[i]);
            if(nxt==-1)
                ;
            else if(nxt==0)
            {
                mn[i]=1;
                ml[i]=i+1;
            }
            else
            {
                mn[i]=mn[nxt-1]+1;
                ml[i]=i-nxt+1+ml[nxt-1];
            }
        }
//        cout<<mn[i]<<' ';
    }
//    cout<<endl;
}

int main()
{
	long n;	//under 1900
	string data;
	cin>>n;
	cin>>data;

/*    for(long i=0;i<n;i++)
        cout<<i+1<<' ';
        cout<<endl;
        for(long i=0;i<n;i++)
        cout<<data[i]<<' ';
        cout<<endl;*/

	init(n,data);
	solve(n,data);
	cnt(n);

	cout<<ans<<endl;
	return 0;
}