自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:53:04，当前版本为作者最后更新于2023-12-10 20:30:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

比较有趣的题目。

猜结论很简单：根据数据范围容易想到会出现循环节，于是用哈希和 $\text{map}$ 暴力求字符串，很快就能找到出现循环的位置并通过本题。

不过我们需要一个更严谨的说法（）于是下面给出简要的分析证明。

• 结论 1.1：若某长为 $k$ 的字符串 $Q$ 在 $s$ 中多次出现，记其出现位置分别为 $p_1< p_2< \dots < p_c< n< p_{c+1}< p_{c+2}\dots< p_d$，则 $s_{p_{c+1}+1}=s_{p_{c+2}+1}=\dots=s_{p_d+1}$。

  （原因：每次操作都不改变“紧跟在 $Q$ 后面出现的字符”的众数。）

• 结论 1.2：若 $s[i-k+1,i]=s[j-k+1,j]\ (n\leq i<j)$，则 $j-i$ 是 $s[i-d+1,+\infty]$ 的循环节。

  （原因：由前文知每种串后面出现的字符固定。）

• 结论 2：若 $s[i-k+1,i]\ (n\leq i)$ 在 $s[1,i-1]$ 中出现，则每个 $s[j-k+1,j]\ (j\geq i)$ 都在 $s[1,j-1]$ 中出现。

  （原因：显然 $s[i-k,i+1]$ 会在 $s[1,i]$ 中出现，于是由数学归纳法可知其正确性。）

• 结论 3：若 $s[i-k+1,i]$ 在 $s[1,i-1]$ 中出现，则第一次出现循环节的最晚位置是 $2i-k$。

  （原因：$s[i-k+1,i]$ 以后每个长为 $k$ 的子串都在之前出现过，而这之前长为 $k$ 的子串至多只有 $i-k$ 种，故在 $i+(i-k)+1$ 之前必然会出现重复，这也代表着循环节的出现。）

• 结论 $4$：若 $\forall n\leq i\leq n+k$，$s[i-k+1,i]$ 都不在 $s[1,i-1]$ 中出现，则第一次出现循环节的最晚位置是 $n+k+1$。

  （原因：显然这意味着 $s_{n+1}=s_{n+2}=\dots=s_{n+k+1}=\texttt{a}$，即 $s[n+1,n+k]=s[n+2,n+k+1]$，即出现了循环节。）

• 最终结论：

  综上可知，第一次出现循环节的最晚位置是 $2(n+k)-k\leq 3n$，暴力哈希的时间复杂度正确，可以通过本题。

代码

数据卡了自然溢出，需要使用双模哈希。

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define mod1 998244353
#define mod2 1000000007
#define B 13331

int n,k,a,b,mx[3000005],cnt[1000005][27],cntd;
char s[3000005];
int cf1[1000005],hs1[3000005],cf2[1000005],hs2[3000005];
unordered_map <int,int> bh,cx;

int geths1(int l,int r)
{
	return (hs1[r]-hs1[l-1]*cf1[r-l+1]%mod1+mod1)%mod1;
}
int geths2(int l,int r)
{
	return (hs2[r]-hs2[l-1]*cf2[r-l+1]%mod2+mod2)%mod2;
}

signed main()
{
	//freopen("P9922_12.in","r",stdin);
	cin>>n>>k>>a>>b>>s;
	for(int i=0;i<=n;i++) mx[i]=1;
	cf1[0]=1; for(int i=1;i<=n;i++) cf1[i]=cf1[i-1]*B%mod1;
	cf2[0]=1; for(int i=1;i<=n;i++) cf2[i]=cf2[i-1]*B%mod2;
	for(int i=1;i<=n;i++) hs1[i]=(hs1[i-1]*B+s[i-1])%mod1;
	for(int i=1;i<=n;i++) hs2[i]=(hs2[i-1]*B+s[i-1])%mod2;
	for(int i=k;i<n;i++)
	{
		int nhs=geths1(i-k+1,i)*1000000007+geths2(i-k+1,i); if(!bh.count(nhs)) bh[nhs]=++cntd;
		int nr=bh[nhs]; cnt[nr][s[i]-'a'+1]++; 
		if(cnt[nr][s[i]-'a'+1]>cnt[nr][mx[nr]]||cnt[nr][s[i]-'a'+1]==cnt[nr][mx[nr]]&&s[i]-'a'+1<mx[nr]) mx[nr]=s[i]-'a'+1;
	}
	for(int i=n+1;i<=3*n;i++)
	{
		int nhs=geths1(i-k,i-1)*1000000007+geths2(i-k,i-1); int nr=bh[nhs]; 
		s[i-1]=(char)(mx[nr]+'a'-1); hs1[i]=(hs1[i-1]*B+s[i-1])%mod1; hs2[i]=(hs2[i-1]*B+s[i-1])%mod2;
		if(cx[nhs])
		{
			int wz=cx[nhs]; int cd=i-wz;
			//cout<<wz<<" "<<i<<endl; return 0;
			for(int j=a;j<=b;j++)
			{
				if(j<=i) cout<<s[j-1];
				else cout<<s[wz+(j-wz)%cd-1];
			}
			cout<<endl; return 0;
		}
		else cx[nhs]=i;
	}
}