描述

---

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。

小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列，相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。

小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少？

输入

第一行两个整数 N和K。1≤N≤20000 1≤K≤N

接下来有 N 个整数，表示每个音的数字。1≤数字≤100

输出

一行一个整数，表示答案。

样例输入

8 212323231

样例输出

4

题解

---

后缀数组主要利用三个映射解决字符串问题

以v[i]表示i~n的后缀字符串

rank[i] 以v[i]为下标，表示v[i]在所有后缀字符串里面的排名

sa[i]以排名为下标，表示排名第i的是sa[i]（即某个v[i]）

height[i]以排名为下标，表示排名i与排名i-1的后缀字符串的最长公共子串。

对于此题，只需二分答案，可以线性check其正确性，

就是相邻排名的串height都大于mid，那么这一系列的串都满足这个答案，累计出现次数即可。

#include 
    
     #define ll long long#define inf 1000000000#define PI acos(-1)#define bug puts("here")#define REP(i,x,n) for(int i=x;i<=n;i++)#define DEP(i,n,x) for(int i=n;i>=x;i--)#define mem(a,x) memset(a,x,sizeof(a))using namespace std;inline int read(){    int x=0,f=1;    char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}const int N=100005;int n,m;int a[N],h[N];int v[N];int sa[2][N],rk[2][N];int p,q,k;void calsa(int sa[N],int rk[N],int SA[N],int RK[N]){    for(int i=1; i<=n; i++)v[rk[sa[i]]]=i;    for(int i=n; i; i--)        if(sa[i]>k)            SA[v[rk[sa[i]-k]]--]=sa[i]-k;    for(int i=n-k+1; i<=n; i++)SA[v[rk[i]]--]=i;    for(int i=1; i<=n; i++)        RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);}void work(){    p=0,q=1;    for(int i=1; i<=n; i++)v[a[i]]++;    for(int i=1; i<=30; i++)v[i]+=v[i-1];    for(int i=1; i<=n; i++)        sa[p][v[a[i]]--]=i;    for(int i=1; i<=n; i++)        rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);    for(k=1; k
     
      0)k--;        }}bool check(int mid){    int res;    REP(i,1,n){        res=1;        while(h[i]>=mid&&i<=n) res++,i++;        if(res>=m) return true;    }    return false;}int main(){    n=read();m=read();    REP(i,1,n) a[i]=read();    work();geth();    int l=0,r=n,ans=0;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid)) l=mid+1,ans=mid;        else r=mid-1;    }    printf("%d\n",ans);    return 0;}