前言

模拟赛里碰到的，但是距离正解还是差一步。遗憾。

Solution

设 $n=|S|$。

先考虑一个比较暴力的办法，枚举 $|t|$，设为 $k$，对每个 $k$ 分别计算答案。

问题转化成，在原串上最多能选出多少个互不重叠且长度为 $k$ 的连续子串。我们依此定义 $f(k)$。

答案为 $\min_{i=1}^{K}(\{|S|-f(i)\times (i-1) \})$。

$f(k)$ 使用哈希可简单计算，时间复杂度 $O(nK)$。

不难注意到，$f(k)$ 是一个单调不升的函数。且由互不重叠，显然有 $f(k)\le \lfloor\frac{n}{k}\rfloor$。（赛时止步于此）

上面两个性质可以推出 $f(k)$ 至多只有 $O(\sqrt n)$ 种不同的取值。

因此我们可以使用二分计算出每一个相等的连续段。时间复杂度 $O(n\sqrt n\log n)$，跑的非常满。

接下来是卡常时间。

但是哈希的常数巨大。

可以考虑使用后缀数组中的 $height$ 数组优化计算。

对于两个长度为 $k$ 且相等的子串，其对应的后缀的 $\operatorname{LCP}$ 显然应该大于等于 $k$，对应区间内的 $height$ 均不小于 $k$。

所以我们把 $height$ 数组内所有大于等于 $k$ 的拆成若干连续段，然后就可以记录每一个后缀对应的上一次出现的位置，和哈希一样简单贪心即可，常数比哈希小了不少。

然后发现仍然无法通过本题。

一种办法是继续往死里卡常：

• 对于 $2k>n$ 的 $k$，答案显然为 $1$。
• 如果当前左端点的函数值为 $1$，则之后显然都为 $1$。
• $O(\sqrt n)$ 种数分到 $n$ 长的序列上，每种数期望有 $O(\sqrt n)$ 个。可以利用这个判断应该在左边还是在右边二分。

（膜拜 zrl123456 大神/bx）

或者考虑另一种常数非常小的方式，使用一个分治状物，当左右端点值相等时返回。但是题解区讲这个办法的大佬已经讲的非常详细了，我就不重复讲了）

最终复杂度 $O(n\sqrt n\log n)$，小常数可以通过。

Code

:::info[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;

int n;
int a[200010];

int sa[200010];
int xx[400010],yy[400010];
int bkt[200010];

int height[200010];

void calc_SA(int m){
    for(int i=1;i<=n;i++) xx[i]=a[i];

    for(int i=1;i<=n;i++) bkt[xx[i]]++;
    for(int i=1;i<=m;i++) bkt[i]+=bkt[i-1];
    for(int i=n;i>=1;i--) sa[bkt[xx[i]]--]=i;

    for(int k=1;k<=n;k<<=1){
        int cnt=0;
        for(int i=n-k+1;i<=n;i++) yy[++cnt]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) yy[++cnt]=sa[i]-k;
        
        for(int i=1;i<=m;i++) bkt[i]=0;
        for(int i=1;i<=n;i++) bkt[xx[i]]++;
        for(int i=1;i<=m;i++) bkt[i]+=bkt[i-1];
        for(int i=n;i>=1;i--) sa[bkt[xx[yy[i]]]--]=yy[i];

        swap(xx,yy);
        cnt=1,xx[sa[1]]=1;
        for(int i=2;i<=n;i++) xx[sa[i]]=(yy[sa[i]]==yy[sa[i-1]]&&yy[sa[i]+k]==yy[sa[i-1]+k]?cnt:++cnt);
        if(cnt==n) break;
        m=cnt;
    }

    for(int i=1,k=0;i<=n;i++){
        if(k) k--;
        if(xx[i]==1) continue;
        while(a[i+k]==a[sa[xx[i]-1]+k]) k++;
        height[xx[i]]=k;
    }
}

int m;

int mem[200010];
int g[200020],lst[200010],dp[200010];

static inline int calc(int k){
    if(k*2>n) return mem[k]=1;
    if(mem[k]) return mem[k];

    g[1]=1;
    int cnt=1;
    for(int i=2;i<=n;i++){
        if(height[i]<k) cnt++;
        g[i]=cnt;
    }

    for(int i=1;i<=n;i++) lst[i]=-inf,dp[i]=0;
    for(int i=1;i<=n;i++){
        if(lst[g[xx[i]]]+k<=i){
            lst[g[xx[i]]]=i;
            dp[g[xx[i]]]++;
        }
    }

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[i]);

    return mem[k]=res;
}

int solve(int K,string S){
    m=K;
    string s;s=S;
    n=s.length(),s=' '+s;

    int sq=sqrt(n);

    for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
    calc_SA(26);

    for(int pl=1;pl<=m;){
        if(calc(pl)==1){
            for(int i=pl;i<=m;i++) mem[i]=1;
            break;
        }

        int l,r;
        if(calc(min(pl+sq,m))==calc(pl)) l=min(pl+sq,m),r=m;
        else l=pl,r=min(pl+sq,m)-1;

        while(l<r){
            int mid=(l+r+1)>>1;
            if(calc(mid)==calc(pl)) l=mid;
            else r=mid-1;
        }

        for(int i=pl;i<=l;i++) mem[i]=mem[pl];
        pl=l+1;
    }

    int ans=inf;
    for(int i=1;i<=m;i++) ans=min(ans,n-mem[i]*(i-1));
    return ans;
}

:::