【CF1063F】String Journey 哈希

题目大意

　　给你一个字符串 \(s\)，让你找出最大的 \(k\)，满足：能从 \(s\) 中选出 \(k\) 个不重叠的字符串 \(t_1,t_2,\ldots,t_k\)，且 \(\forall i,\lvert t_i\rvert >\lvert t_{i+1}\rvert\)，\(t_{i+1}\) 是 \(t_i\) 的子串，\(t_{i+1}\) 的出现位置在 \(t_i\) 后面。

　　\(n\leq 500000\)

题解

　　显然最优方案中 \(t_{i+1}\) 就是把 \(t_i\) 的第一个字符或最后一个字符删掉得到的。

　　记 \(f_i\) 为从 \(i\) 开始的后缀，选一个前缀作为 \(t_1\) 所能得到的最大的 \(k\)。

　　那么可以二分 \(f_i\)，然后判断 \(s_{i\sim i+f_i-1}\) 删掉前缀/后缀之后得到的字符串在后面任意一次出现的位置的 \(f\) 值是否 \(\geq f_i-1\)。

　　这样是 \(O(n\log^2 n)\) 的。

　　可以发现 \(f_i\leq f_{i+1}+1\)。因为如果 \(f_i>f_{i+1}+1\)，那么把 \(f_i\) 的第一个字符扣掉就会得到一个开头在 \(i+1\)，长度为 \(f_i-1\) 的方案。这样就不需要二分了。

　　时间复杂度： \(O(n\log n)\)

　　还有一种做法：

　　注意到答案 \(\leq O(\sqrt n)\)，那么就可以枚举每个长度 \(\leq 1000\) 的字符串，然后用哈希判断。

　　时间复杂度：\(O(n\sqrt n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<functional>

#include<cmath>

#include<vector>

#include<unordered_set>

//using namespace std;

using std::min;

using std::max;

using std::swap;

using std::sort;

using std::reverse;

using std::random_shuffle;

using std::lower_bound;

using std::upper_bound;

using std::unique;

using std::vector;

using std::unordered_set;

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

typedef std::pair<int,int> pii;

typedef std::pair<ll,ll> pll;

void open(const char *s){

#ifndef ONLINE_JUDGE

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

void open2(const char *s){

#ifdef DEBUG

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}

void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}

int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}

int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}

const int N=500010;

bool f[1010][N];

bool s[7000007];

char str[N];

int n;

int h[N];

int main()

{

	open("f");

	scanf("%d",&n);

	scanf("%s",str+1);

	int ans=1;

	memset(f[1],1,sizeof f[1]);

	for(int j=1;j<=n;j++)

		h[j]=str[j]-'a'+1;

	for(int i=2;i<=1000;i++)

	{

		memset(s,0,sizeof s);

		for(int j=n-i+1;j>=1;j--)

		{

			if(j+i<=n&&f[i-1][j+i])

				s[h[j+i]]=1;

			if(s[h[j]]||s[h[j+1]])

			{

				ans=i;

				f[i][j]=1;

			}

		}

		for(int j=1;j<=n-i+1;j++)

			h[j]=(h[j]*129+str[j+i-1]-'a'+1)%7000007;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

【CF1063F】String Journey 哈希

题目大意

题解

代码

最新文章

热门文章