【题意】求最长的出现至少k次的子串。

【算法】后缀数组+单调队列

【题解】求出所有LCP，然后SA上每k个找一个最小值，取所有最小值中的最大值。

移动区间最小值，显然可以用单调队列优化。

注意：队列左闭右开时，访问队尾一定要tail-1。

求LCP时，只能按字符串顺序求才满足O(n)的规律。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=20010,maxM=1000001;int sa[maxn],base[maxM],x[maxn],y[maxn],n,s[maxn],h[maxn],kind;struct cyc{
    int p,x;}q[maxn];void SA_build(int m){    for(int i=1;i<=n;i++)base[x[i]=s[i]+1]++;    for(int i=2;i<=m;i++)base[i]+=base[i-1];    for(int i=n;i>=1;i--)sa[base[x[i]]--]=i;    for(int k=1;k<=n;k<<=1){        int p=0;        for(int i=n-k+1;i<=n;i++)y[++p]=i;        for(int i=1;i<=n;i++)if(sa[i]>k)y[++p]=sa[i]-k;        for(int i=1;i<=m;i++)base[i]=0;        for(int i=1;i<=n;i++)base[x[i]]++;        for(int i=2;i<=m;i++)base[i]+=base[i-1];        for(int i=n;i>=1;i--)sa[base[x[y[i]]]--]=y[i];        swap(x,y);        p=1;x[sa[1]]=1;        for(int i=2;i<=n;i++)if(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])x[sa[i]]=p;else x[sa[i]]=++p;        m=p;    }    int p=0;    for(int i=1;i<=n;i++){        if(p)p--;        int j=sa[x[i]-1];        while(s[i+p]==s[j+p])p++;        h[x[i]]=p;    }}    int main(){    scanf("%d%d",&n,&kind);    for(int i=1;i<=n;i++)scanf("%d",&s[i]);    SA_build(maxM);    int head=0,tail=1;q[head]=(cyc){
    2,h[2]};    int ans=0;    for(int i=3;i<=n;i++){        if(q[head].p-1
         
          head&&q[tail-1].x>=h[i])tail--;        q[tail++]=(cyc){i,h[i]};        ans=max(ans,q[head].x);    }    printf("%d",ans);    return 0;}