专栏文章

题解：P9873 [EC Final 2021] Beautiful String

MMeta_Morph
P9873题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0hpbf
此快照首次捕获于
2025/12/02 11:21
3 个月前
此快照最后确认于
2025/12/02 11:21
3 个月前
查看原文

P9873 [EC Final 2021] Beautiful String 题解

博客园链接：P9873 [EC Final 2021] Beautiful String 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

字符串，LCP，Hash，KMP。

分析

首先我们知道 A,B,C,D,E,FA,B,C,D,E,F 六个非空子串中，A=B=E,C=FA=B=E,C=F，那么 BC=EFBC=EF，我们设 G=BC=EFG=BC=EF，那么原串可以表示为 AGDGAGDG。
考虑以某种方法求出 GDGGDG 的方案，再以某种方法用 AA 与 GG 的关联来统计答案。

法 1：LCP

考虑设 sumi,jsum_{i,j} 表示 GDGGDG 的左端点在 ii，其中 GG 的长度 >j>j 的方案数，那么这个很好求，在 O(n2)O(n^2) 求 LCP 的时候顺便求出。
设 LCPi,jLCP_{i,j} 表示 LCP(Si,Sj)LCP(S_i,S_j)，其中 SiS_i 表示 SS 从第 ii 个字符开始的后缀，那么 O(n2)O(n^2) 可以求出，然后搭配 ∣G∣<j−i|G|<j-i 的限制，我们就可以统计 sumsum。
最后考虑用 AA 来统计总的答案，其实也就是在求 LCP 的过程中求出。

法 2：Hash + KMP

我们还是像上述过程一样求 sumi,jsum_{i,j} 表示 GDGGDG 的左端点在 ii，其中 GG 的长度 >j>j 的方案数。不过由于没有了 LCP 的辅助，我们 AA 与 GG 的相同长度关系要用 Hash 求。
考虑新定义 KMP，我们先求出最原始的 next 数组（失配指针），然后我们再重新来一遍，求 Nxt 表示满足长度小于 12\frac{1}{2} 现在长度的最长 border，那么只要把更新的数组换掉，再加入长度限制即可解决。
其余统计较为简单。

代码

法 1：LCP

这种方法常数较小。
CPP
constexpr int N(5e3+10);

char S[N];
int Cas,n;
int lcp[N],s[N];
int sum[N][N];
ll ans;

int Cmain() {
	scanf("%s",S),n=strlen(S),ans=0;
	DOR(i,n-1,0) {
		FOR(j,0,n)s[j]=0;
		FOR(j,0,n)sum[i][j]=0;
		FOR(j,i+1,n-1) {
			if(S[i]==S[j]) {
				lcp[j]=(j+1<n?lcp[j+1]+1:1);
				if(i+lcp[j]>=j)ans+=sum[j][j-i];
				int r(min(j-i-1,lcp[j]));
				sum[i][0]+=r,--s[0],++s[r];
			} else lcp[j]=0;
		}
		FOR(j,1,((n-i-1)>>1)-1)sum[i][j]+=sum[i][j-1]+s[j-1],s[j]+=s[j-1];
	}
	O(ans,'\n');
	return 0;
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	for((Cas=1); Cas; --Cas)Cmain();
	return 0;
}

法 2：Hash + KMP

CPP
constexpr int N(5e3+10),B1(131),P1(1e9+7),B2(13331);
constexpr Piu B(B1,B2);

char s[N];
int Cas,n;
int nxt[N],Nxt[N];
ll ans;
ll cnt[N];
/*Hash*/
Piu pw[N],h[N];

Piu operator -(Piu A,Piu B) {
	return Piu(A.Fi-B.Fi<0?A.Fi-B.Fi+P1:A.Fi-B.Fi,A.Se-B.Se);
}

Piu operator +(Piu A,Piu B) {
	return Piu(A.Fi+B.Fi>=P1?A.Fi+B.Fi-P1:A.Fi+B.Fi,A.Se+B.Se);
}

Piu operator *(Piu A,Piu B) {
	return Piu((ll)A.Fi*B.Fi%P1,A.Se*B.Se);
}

Piu Q(int l,int r) {
	return h[r]-h[l-1]*pw[r-l+1];
}

void Init() {
	pw[0]=Piu(1,1);
	FOR(i,1,n)pw[i]=pw[i-1]*B;
	FOR(i,1,n)h[i]=h[i-1]*B+Piu(s[i],s[i]);
}
/*Solve*/
void Solve(int S) {
	auto len=[&](int i) { return i-S+1; };
	/*DE("nxt");*/
	int it(nxt[S-1]=S-2);
	FOR(i,S,n) {
		while(it>=S-1&&s[i]!=s[it+1])it=nxt[it];
		nxt[i]=++it;
	}
	/*DE("Nxt");*/
	it=Nxt[S-1]=S-2;
	FOR(i,S,n) {
		while(it>=S-1&&(s[i]!=s[it+1]||len(it+1)*2>=len(i)))it=nxt[it];
		Nxt[i]=++it;
	}
	/*DE("Count");*/
	FOR(i,0,len(n))cnt[i]=0;
	FOR(i,S,n)++cnt[len(Nxt[i])];
	DOR(i,n,S)cnt[len(nxt[i])]+=cnt[len(i)];
	DOR(i,len(n)-1,0)cnt[i]+=cnt[i+1];
	FOR(i,1,min(S-1,n-S+1))if(Q(S-i,S-1)==Q(S,S+i-1))ans+=cnt[i+1];
}

int Cmain() {
	scanf("%s",s+1),n=strlen(s+1),Init(),ans=0;
	FOR(i,2,n)Solve(i);
	O(ans,'\n');
	return 0;
}
/*Main*/
signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	for((Cas=1); Cas; --Cas)Cmain();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...