自动搬运

查看原文

来自洛谷，原作者为

	meyi 明日黄花

搬运于2025-08-24 22:52:37，当前版本为作者最后更新于2023-11-23 14:53:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

2023/11/30 upd: 感谢 zyc212303 指出一处 typo。

貌似写了个常数比较小的做法，目前洛谷最优解 rk1 390ms，比 rk2 825ms 快了一倍。

首先由 $s_2=s_5, s_3=s_6$ 可知 $s_2+s_3=s_5+s_6$，不妨将它们合并起来看，那么题意就转化为了：定义字符串 $t$ 是美丽的当且仅当将可以 $t$ 视作 $t_1+t_2+t_3+t_4$，满足 $t_1,t_2,t_3,t_4$ 均非空，且 $t_1$ 为 $t_2$ 的真前缀，$t_2=t_4$，给定字符串 $s$，求其有多少子串是美丽的。

考虑 $O(n^2)$ 求 $\text{lcp}$ 的过程，若 $i$ 和 $j$ 的 $\text{lcp}$ 为 $k$，那么可以将 $t_2$ 视作 $s_{i..i+l-1}$，将 $t_4$ 视作 $s_{j,j+l-1}$，$(1\le l\le k)$，由于 $t_3$ 的存在，因此还需要满足 $l< j-i$。故我们可以预处理 $sum_{i,l}$ 表示以 $i$ 开头长度为 $>l$ 的选择 $t_2$ 和 $t_4$ 的方案数，那么每个 $j$ 给 $sum_i$ 的贡献是一个等差数列的形式，使用两个前缀和数组处理即可。最后注意到这里的 $t_2$ 是唯一确定的，因此不会重复计数。

然后考虑 $t_1$ 怎么枚举，仍然是在求 $\text{lcp}$ 的过程中，设 $i$ 和 $j$ 的 $\text{lcp}$ 为 $k$，若 $i+k\ge j$，则说明 $s_{i,j-1}$ 可以成为 $t_1$，答案只需累加 $sum_{j,j-i}$ 即可。

时间复杂度 $O(n^2)$。

代码：

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
int main(){
	int t_case=1;
	cin>>t_case;
	while(t_case--){
		string s;
		cin>>s;
		ll ans=0;
		int n=s.size();
		V<int>lcp(n);
		V<V<int>>sum(n);
		Rep(i,n){
			sum[i].resize(n-i-1>>1);
			V<int>sum2(sum.size());
			FOR(j,i+1,n){
				if(s[i]==s[j]){
					lcp[j]=(j+1<n?lcp[j+1]:0)+1;
					if(i+lcp[j]>=j&&j-i<sum[j].size())ans+=sum[j][j-i];
					if(sum[i].size()){
						int ed=min(j-i-1,lcp[j]);
						sum[i][0]+=ed,--sum2[0];
						if(ed<sum[i].size())++sum2[ed];
					}
				}
				else lcp[j]=0;
			}
			FOR(j,1,sum[i].size())sum[i][j]+=sum[i][j-1]+sum2[j-1],sum2[j]+=sum2[j-1];
		}
		printf("%lld\n",ans);
	}
	return 0;
}