P9922 题解

honglan0301 · 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;
    }
}