Milk Patterns – poj 3261 （求重复k次的最长子串）

题目大意：给你一个数组，求这个数组里面至少重复k次的子串。 分析：后缀数组的练手题目…不过给的数字比较大，可以先离散化处理一下即可。 代码如下：===============================================================================================================================

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;const int MAXN = 2e4+;struct SuffixArr
{
    int tempx[MAXN], tempy[MAXN], text[MAXN], Hash[MAXN];
    int rank[MAXN], sa[MAXN], sum[MAXN], height[MAXN];
    int *x, *y, N, MaxId;    void GetText(int data[], int len)
    {
        N = len, x=tempx, y=tempy;        for(int i=; i<N; i++)
            Hash[i] = data[i];        sort(Hash, Hash+N);
        MaxId = unique(Hash, Hash+N) - Hash;        for(int i=; i<N; i++)
        {
            text[i] = x[i] = lower_bound(Hash, Hash+MaxId, data[i])-Hash;
            y[i] = i;
        }
    }
    bool cmp(int i, int len)
    {
        if(sa[i]+len > N || sa[i-]+len > N)
            return false;
        if(y[sa[i]]!=y[sa[i-]] || y[sa[i]+len]!=y[sa[i-]+len])
            return false;        return true;
    }
    void BaseSort()
    {
        for(int i=; i<MaxId; i++)
            sum[i] = ;
        for(int i=; i<N; i++)
            sum[ x[ y[i] ] ] += ;
        for(int i=; i<MaxId; i++)
            sum[i] += sum[i-];
        for(int i=N-; i>=; i--)
            sa[ --sum[ x[ y[i] ] ] ] = y[i];
    }
    void GetSa()
    {
        BaseSort();        for(int len=; len <= N; len<<=)
        {
            int id = ;            for(int i=N-len; i<N; i++)
                y[id++] = i;
            for(int i=; i<N; i++)if(sa[i] >= len)
                y[id++] = sa[i] - len;            BaseSort();
            swap(x, y);
            x[ sa[] ] = id = ;            for(int i=; i<N; i++)
            {
                if(cmp(i, len) == true)
                    x[sa[i]] = id;
                else
                    x[sa[i]] = ++id;
            }            MaxId = id+;            if(MaxId >= N)
                break;
        }
    }
    void GetHeight()
    {
        for(int i=; i<N; i++)
            rank[sa[i]] = i;      ///  debug(text);
      ///  debug(rank);        for(int k=, i=; i<N; i++)
        {
            if(!rank[i])
            {
                height[] = k = ;
                continue;
            }
            if(k)k--;            int pre = sa[ rank[i]- ];            while(text[i+k] == text[pre+k])
                k++;
            height[rank[i]] = k;
        }        ///debug(height);
    }
    void debug(int p[])
    {
        for(int i=; i<N; i++)
            printf("%d ", p[i]);
        printf("\n");
    }
};SuffixArr suf;
int data[MAXN];bool Find(int times, int k)
{
    int cnt=;    for(int i=; i<suf.N; i++)
    {
        if(suf.height[i] < k)
            cnt = ;
        else
        {
            cnt += ;
            if(cnt == times-)
                return true;
        }
    }    return false;
}int main()
{
    int N, times;    while(scanf("%d%d", &N, &times) != EOF)
    {
        for(int i=; i<N; i++)
            scanf("%d", &data[i]);
        data[N] = -;        suf.GetText(data, N+);
        suf.GetSa();
        suf.GetHeight();        int L=, R=N, ans=;        while(L <= R)
        {
            int Mid = (L+R)>>;            if(Find(times, Mid) == true)
            {
                ans = Mid;
                L = Mid + ;
            }
            else
                R = Mid - ;
        }        printf("%d\n", ans);
    }    return ;
}