权限题。

题意：

求一个字符串中出现超过k次的最长子串，可重叠

（n<=20000）

Solution：

先用后缀数组跑出height

然后我们知道一个性质：任意两个后缀的最长公共前缀就是它们之间所有height取min

那么这个问题就相当于枚举每个长为k-1的区间，在区间内部求min，每个区间求max，倍增解决即可

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=20010;
int m,n,kk,a[N],p;
int tax[1000000],SA[N],tp[N],rk[N],height[N][21];
int num[N],mi[20];
void Jsort()
{
    for (int i=0;i<=m;i++) tax[i]=0;
    for (int i=1;i<=n;i++) tax[rk[tp[i]]]++;
    for (int i=1;i<=m;i++) tax[i]+=tax[i-1];
    for (int i=n;i>=1;i--) SA[tax[rk[tp[i]]]--]=tp[i];
}
bool cmp(int tp[],int i,int j,int w)
{
    return (tp[i]==tp[j]&&tp[i+w]==tp[j+w]);
}
int main()
{
    scanf("%d%d",&n,&kk);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        rk[i]=a[i],tp[i]=i;m=max(a[i],m);
    }
    Jsort();
    for (int w=1;p<n;w+=w,m=p)
    {
        p=0;
        for (int i=n-w+1;i<=n;i++) tp[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>w) tp[++p]=SA[i]-w;
        Jsort();swap(rk,tp);
        p=1;rk[SA[1]]=p;
        for (int i=2;i<=n;i++)
            if (cmp(tp,SA[i],SA[i-1],w)) rk[SA[i]]=p;else rk[SA[i]]=++p;
    }
    int k=0;
    for (int i=1;i<=n;i++)
    {
        if (rk[i]==1) {height[1][0]=0;continue;}
        if (k) k--;
        int j=SA[rk[i]-1];
        while (a[i+k]==a[j+k]&&i+k<=n&&j+k<=n) k++;
        height[rk[i]][0]=k;
        //cout<<rk[i]<<" "<<k<<endl;
    };
    mi[0]=1;for (int i=1;i<=20;i++) mi[i]=mi[i-1]*2;
    for (int i=1;i<=20;i++)
        for (int j=2;j<=n;j++)
        {
            height[j][i]=min(height[j][i-1],height[min(j+mi[i-1],n)][i-1]);
            //cout<<j<<" "<<i<<" "<<height[j][i]<<endl;
        }
    kk--;
    int ans=0;

    for (int j=2;j<=n-kk+1;j++)
    {
        int nw=kk,pos=j,tot=n;
        for (int i=20;i>=0;i--)
            if (nw>=mi[i]) tot=min(tot,height[min(n,pos)][i]),nw-=mi[i],pos+=mi[i];
        ans=max(ans,tot);
    }
    printf("%d",ans);
}