统计部分n次，通过 略加优化地跳跃 寻找上一个合法且相同的字符，个人感觉 最坏复杂度是n^2,优化也只是常数层面的 ，但是在官方数据下AC，故来求助谷民:请问这段代码的复杂度如何，为什么如此优化后(在gtnxt中借助nx寻找下一个字)可以AC而暴力跳(在gtnxt中线性寻找下一个字)不可以

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

long ans=0;
long nx[2000005]; //以类似链式前向星的方法存储下一个相同的字
long mn[2000005]; //以data[i]为字符串结尾，最多匹配mn[i]个字串
long ml[2000005]; //以data[i]为字符串结尾，最长可以匹配长度为ml[i]的字串

void init(long n,char* data)
{
    int tmp[26];

	for(long i=0;i<26;i++)
    {
        tmp[i]=-1;
    }
    for(int i=0;i<n;i++)
    {
        nx[i]=tmp[data[i]-'a'];
        tmp[data[i]-'a']=i;
    }
}

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

long getnxt(char* data,long l,long r,const char e)//e是旧版本(线性查找)的残留，现在没有意义
{
    for(long i=nx[r+1];i>=l;i=nx[nx[i]])
    {
        if(r-i==ml[r]-ml[i])
            return i;
    }
    return -1;
}

void solve(long n,char* data)
{
    
    if(data[0]==data[1])
        mn[1]=1,ml[1]=2;
    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];
            }
        }
    }
}

int main()
{
	long n;
	char data[2000005];
	cin>>n;
	cin>>data;

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

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