按照第一篇题解的思路的第一部分，没加h数组的优化打出了一份代码，按题解中的说法是会被极端数据卡到n^2，但我一交上去发现过了。。。

是ccf数据不强，还是题解时间复杂度分析有误？

如果是前者建议添加hack，后者建议题解改动。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum=0,f[2000005],g[2000005];
string s;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s;
	for(int i=1; i<n; i++) {
		g[i]=i-1;
		while(g[i]>=0&&s[i]!=s[g[i]])g[i]=g[g[i]]-1;
		if(g[i]>=0)f[i]=f[(g[i]!=0?g[i]-1:0)]+1;
		sum+=f[i];
	}
	cout<<sum;
	return 0;
}

难不成是时间复杂度均摊了？求助大佬。。。