CF1063F String Journey

CF1063F String Journey

洛谷CF1063F String Journey

题目大意

对于一个字符串数组$t_1,t_2,\dots ,t_k$，如果对于每个$t_i$都是$t_{i?1}$的真子串的话（即$t_i$是$t_{i?1}$的子串且$t_i\ne t_{i?1}$），则称这个字符串数组为有序数组。

给定字符串$S$，要求构造有序串组$t_1,t_2,\dots ,t_k$和任意字符串组$u_1,u_2,\dots ,u_k,u_{k+1}$，使得$S=u_1+t_1+?+u_k+t_k+u_{k+1}$（其中$+$为字符串的拼接）。求所有构造方案中$k$的最大值。

$1\le n\le 5\times 10^5$

题解

假设答案为$ans$，那么一定存在使得$t_1,t_2,\dots ,t_{ans}$的长度为$ans,ans?1,\dots ,1$的构造方法。那么，因为$ans+(ans?1)+?+1\le n$，得$ans\le \sqrt{2n}$。

从小到大枚举$ans$，设$f_i$表示当答案为$ans$时$t_1$以$i$开头是否可行。

记$sum=\sum _{i=1}^{ans}i$，则可行的$i$一定满足$i\le n?sum+1$。我们从大到小枚举$i$，并不断向哈希表中加入长度为$ans?1$且不与$[i,i+ans?1]$重叠的串，对$f_i$转移的时候查询$[i,i+ans?2]$或$[i+1,i+ans?1]$是否在哈希表中出现过即可。

时间复杂度为$O(n\sqrt{n})$，空间复杂度为$O(n\sqrt{n}+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;
}