f[i] 存的是以第 $i$ 个字符为右端点的\最近的左端点的\左边的位置。
暴力跳怎么也能过？

想了好久不会整时间复杂度。正确性也不太会

#include<bits/stdc++.h>
using namespace std;
const int N=2e6,C=26,S=sizeof(int)*C;
int n,f[N+5],s[N+5];
char c[N+5];
long long ans;
int main(){ 
	scanf("%d%s",&n,c+1);
	for(int i=1;i<=n;++i){
		int x=i-1;
		while(x&&c[x]!=c[i]) x=f[x];
		if(x) f[i]=x-1,ans+=(s[i]=s[x-1]+1);
	}
	printf("%lld",ans);
}