解法来自 CSDN - CSP-S 2023 T2题解，代码如下：

#include<bits/stdc++.h>
typedef long long ll;
const int N=2e6+6;
ll ans=0;
int n,dp[N],last[N];
std::string s;
int find(int pos,char check) {
	if(s[pos]==check) return pos;
	if(!last[pos]) return 0;
	return find(last[pos]-1,check);
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin>>n>>s; s=" "+s;
	for(int i=1;i<=n;++i) {
		last[i]=find(i-1,s[i]);
		if(last[i]) ans+=dp[i]=dp[last[i]-1]+1;
	}
	std::cout<<ans<<'\n';
	return 0;
}

目前各个平台的民间数据都可以通过，但提交到 CF 原题（题意相同，但是数据范围缩小至 3e5，且是多测）会 Time limit exceeded on test 5。

我感觉复杂度是 $O(n)$，即过程里面 find 函数跳 last 最多跳 $n$ 次，难道说这个方法其实是 $n^2$ 的？为什么会 T 呢？如何分析复杂度？

请各位 dalao 帮忙分析下！