BZOJ 1717 [Usaco2006 Dec]Milk Patterns 产奶的模式

题目大意

给你一个长度为N的数组，问出现至少K次的子串最长有多长。

字符串问题没咋做过，但是蛇皮的二分+哈希我可是记得很清楚，大爷讲过这是“字符串最优算法，堪比后缀自动机的强力工具……”

好，既然是要求这个东西，直接二分最长长度，每个mid哈希一下就好了，这个东西如果长度i是可行解，那么必定有i-1也是可行解，满足单调性。使用multiset维护单调性就可以了……1A好开心qwq

#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
#define bsa 131
#define bsb 233
int n,k,inx,ans;
unsigned long long hsa[20010],hsb[20010],a[20010],b[20010];
multiset<pair<unsigned long long,unsigned long long> >s;
bool check(int tx)
{
    ans=0;
    s.clear();
    for(int i=tx;i<=n;++i)
    {
        s.insert(make_pair(hsa[i]-hsa[i-tx]*a[tx],hsb[i]-hsb[i-tx]*b[tx]));
        ans=max(ans,(int)s.count(make_pair(hsa[i]-hsa[i-tx]*a[tx],hsb[i]-hsb[i-tx]*b[tx])));
    }
    return ans>=k;
}
int main()
{
    scanf("%d%d",&n,&k);
    a[0]=b[0]=1;
    for(int i=1;i<=n;++i) a[i]=a[i-1]*bsa,b[i]=b[i-1]*bsb,scanf("%d",&inx),hsa[i]=hsa[i-1]*bsa+inx,hsb[i]=hsb[i-1]*bsb+inx;
    int l=1,r=n+1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    printf("%d\n",l-1);
    return 0;
}