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 ;

}