后缀数组一·重复旋律

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小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

输出

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

样例输入

样例输出

4
分析：后缀数组模板，取连续的k-1个最小中的最大即可；
代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
#define sys system("pause")
#define freopen freopen("in.txt","r",stdin)
const int maxn=2e4+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
inline ll read()
{
    ll x=0;int 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;
}
int n,m,k,t,cntA[maxn],cntB[maxn],sa[maxn],lev[maxn],ch[maxn],height[maxn],A[maxn],B[maxn],tsa[maxn],ans;
void solve()
{
    for (int i = 0; i < 256; i ++) cntA[i] = 0;
    for (int i = 1; i <= n; i ++) cntA[ch[i]] ++;
    for (int i = 1; i < 256; i ++) cntA[i] += cntA[i - 1];
    for (int i = n; i; i --) sa[cntA[ch[i]] --] = i;
    lev[sa[1]] = 1;
    for (int i = 2; i <= n; i ++)
    {
        lev[sa[i]] = lev[sa[i - 1]];
        if (ch[sa[i]] != ch[sa[i - 1]]) lev[sa[i]] ++;
    }
    for (int l = 1; lev[sa[n]] < n; l <<= 1)
    {
        for (int i = 0; i <= n; i ++) cntA[i] = 0;
        for (int i = 0; i <= n; i ++) cntB[i] = 0;
        for (int i = 1; i <= n; i ++)
        {
            cntA[A[i] = lev[i]] ++;
            cntB[B[i] = (i + l <= n) ? lev[i + l] : 0] ++;
        }
        for (int i = 1; i <= n; i ++) cntB[i] += cntB[i - 1];
        for (int i = n; i; i --) tsa[cntB[B[i]] --] = i;
        for (int i = 1; i <= n; i ++) cntA[i] += cntA[i - 1];
        for (int i = n; i; i --) sa[cntA[A[tsa[i]]] --] = tsa[i];
        lev[sa[1]] = 1;
        for (int i = 2; i <= n; i ++)
        {
            lev[sa[i]] = lev[sa[i - 1]];
            if (A[sa[i]] != A[sa[i - 1]] || B[sa[i]] != B[sa[i - 1]]) lev[sa[i]] ++;
        }
    }
    for (int i = 1, j = 0; i <= n; i ++)
    {
        if (j) j --;
        while (ch[i + j] == ch[sa[lev[i] - 1] + j]) j ++;
        height[lev[i]] = j;
    }
}
multiset<int>pq;
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%d",&ch[i]);
    solve();
    rep(i,1,m-1)pq.insert(height[i]);
    ans=*pq.begin();
    rep(i,m,n+1)
    {
        pq.erase(pq.lower_bound(height[i-m+1]));
        pq.insert(height[i]);
        ans=max(ans,*pq.begin());
    }
    printf("%d
",ans);
    //system("Pause");
    return 0;
}