CF1063F String Journey

2023-12-21 22:27:25

CF1063F String Journey

洛谷CF1063F String Journey

题目大意

对于一个字符串数组 t 1 , t 2 , … , t k t_1,t_2,\dots,t_k t1?,t2?,,tk?,如果对于每个 t i t_i ti?都是 t i ? 1 t_{i-1} ti?1?的真子串的话(即 t i t_i ti? t i ? 1 t_{i-1} ti?1?的子串且 t i ≠ t i ? 1 t_i\neq t_{i-1} ti?=ti?1?),则称这个字符串数组为有序数组。

给定字符串 S S S,要求构造有序串组 t 1 , t 2 , … , t k t_1,t_2,\dots,t_k t1?,t2?,,tk?和任意字符串组 u 1 , u 2 , … , u k , u k + 1 u_1,u_2,\dots,u_k,u_{k+1} u1?,u2?,,uk?,uk+1?,使得 S = u 1 + t 1 + ? + u k + t k + u k + 1 S=u_1+t_1+\cdots+u_k+t_k+u_{k+1} S=u1?+t1?+?+uk?+tk?+uk+1?(其中 + + +为字符串的拼接)。求所有构造方案中 k k k的最大值。

1 ≤ n ≤ 5 × 1 0 5 1\leq n\leq 5\times 10^5 1n5×105


题解

假设答案为 a n s ans ans,那么一定存在使得 t 1 , t 2 , … , t a n s t_1,t_2,\dots,t_{ans} t1?,t2?,,tans?的长度为 a n s , a n s ? 1 , … , 1 ans,ans-1,\dots,1 ans,ans?1,,1的构造方法。那么,因为 a n s + ( a n s ? 1 ) + ? + 1 ≤ n ans+(ans-1)+\cdots+1\leq n ans+(ans?1)+?+1n,得 a n s ≤ 2 n ans\leq \sqrt{2n} ans2n ?

从小到大枚举 a n s ans ans,设 f i f_i fi?表示当答案为 a n s ans ans t 1 t_1 t1? i i i开头是否可行。

s u m = ∑ i = 1 a n s i sum=\sum\limits_{i=1}^{ans}i sum=i=1ans?i,则可行的 i i i一定满足 i ≤ n ? s u m + 1 i\leq n-sum+1 in?sum+1。我们从大到小枚举 i i i,并不断向哈希表中加入长度为 a n s ? 1 ans-1 ans?1且不与 [ i , i + a n s ? 1 ] [i,i+ans-1] [i,i+ans?1]重叠的串,对 f i f_i fi?转移的时候查询 [ i , i + a n s ? 2 ] [i,i+ans-2] [i,i+ans?2] [ i + 1 , i + a n s ? 1 ] [i+1,i+ans-1] [i+1,i+ans?1]是否在哈希表中出现过即可。

时间复杂度为 O ( n n ) O(n\sqrt n) O(nn ?),空间复杂度为 O ( n n + P ) O(n\sqrt n+P) O(nn ?+P),其中 P P P为哈希表的大小。

code

#include<bits/stdc++.h>
using namespace std;
const int base=37;
const long long P=19260817;
const int N=500000;
int n,sq,sum,ans;
long long g[N+5];
char s[N+5];
bitset<N+5>f[1005];
bitset<P+5>z;
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		g[i]=s[i]-'a'+1;
	}
	sq=sqrt(2*n)+1;sum=1;
	f[1].set();
	for(ans=2;ans<=sq;ans++){
		sum+=ans;
		for(int i=n-sum+1;i>=1;i--){
			int j=i+ans;
			if(f[ans-1][j]) z[g[j]]=1;
			if(z[g[i]]||z[g[i+1]]) f[ans][i]=1;
		}
		if(!f[ans].count()){
			--ans;break;
		}
		z.reset();
		for(int i=1;i<=n-ans+1;i++){
			g[i]=(g[i]*base%P+s[i+ans-1]-'a'+1)%P;
		}
	}
	printf("%d",ans);
	return 0;
}

文章来源:https://blog.csdn.net/tanjunming2020/article/details/135138186
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。