luogu p2582（后缀数组）

传送门

题意：

给你一个字符串(str)，问出现次数为(k)的最长的子串的长度。

分析：

首先我们先将字符串(str)的所有后缀进行排序，并求出他们两两的(height)数组。

根据(height)数组的含义，(height[i]=lcp(i,i-1))，我们知道，倘若存在一个子串出现了k次，那么必定存在一个连续的区间([l,r],(r-l+1 ge k-1))，使得(lcp(l,r) !=0)。那么我们他们(lcp)中的最小值就是答案。因此我们发现，我们现在要求的是(height)数组中，长度至少为(k-1)的最小值，并要使得最小值最大化。而这个显然是一个经典的划窗问题，我们可以通过单调队列在(mathcal{O}(n))的时间复杂度中求出答案。

故整体的复杂度为(mathcal{O}(nlogn))

代码：

#include <bits/stdc++.h>
#define maxn 20010
using namespace std;
int rk[maxn],sa[maxn],height[maxn],tmp[maxn],cnt[maxn],n,k;
int str[maxn],tot=0;
unordered_map<int,int>mp;
unordered_map<int,bool>vis;
void SA(int n,int m){
    int i,j,k;
    n++;
    for(i=0;i<n+5;i++) rk[i]=sa[i]=height[i]=tmp[i]=0;
    for(i=0;i<m;i++) cnt[i]=0;
    for(i=0;i<n;i++) cnt[rk[i]=mp[str[i]]]++;
    for(i=1;i<m;i++) cnt[i]+=cnt[i-1];
    for(i=0;i<n;i++) sa[--cnt[rk[i]]]=i;
    for(k=1;k<=n;k<<=1){
        for(i=0;i<n;i++){
            j=sa[i]-k;
            if(j<0) j+=n;
            tmp[cnt[rk[j]]++]=j;
        }
        sa[tmp[cnt[0]=0]]=j=0;
        for(i=1;i<n;i++){
            if(rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k])
                cnt[++j]=i;
            sa[tmp[i]]=j;
        }
        memcpy(rk,sa,n*sizeof(int));
        memcpy(sa,tmp,n*sizeof(int));
        if(j>=n-1) break;
    }
    //get height[]
    i=0,k=0,height[0]=0;
    for(j=rk[0];i<n-1;i++,k++){
        while(~k&&mp[str[i]]!=mp[str[sa[j-1]+k]]){
            height[j]=k--;
            j=rk[sa[j]+1];
        }
    }
}
void debug(){
    //ababa
    // sa[1]=4,sa[2]=2,sa[3]=0,sa[4]=3,sa[5]=1
    // rk[0]=3,rk[1]=5,rk[2]=2,rk[3]=4,rk[4]=1
    for(int i=1;i<=n;i++){
        printf("sa[%d]=%d
",i,sa[i]);
    }
    for(int i=0;i<n;i++){
        printf("rank[%d]=%d
",i,rk[i]);
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&str[i]);
        if(!mp[str[i]]) mp[str[i]]=++tot;
    }
    SA(n,tot+1);
    deque<int>que;
    int res=0;
    for(int i=1;i<=n;i++){
        while(!que.empty()&&i-que.front()>=k-1) que.pop_front();
        while(!que.empty()&&height[que.back()]>=height[i]) que.pop_back();
        que.push_back(i);
        if(!que.empty()&&i>=k-1) res=max(res,height[que.front()]);
    }
    printf("%d
",res);
    return 0;
}