题目：http://poj.org/problem?id=3261

仍然是后缀数组的典型应用----后缀数组+lcp+二分

做的蛮顺的，1A

可是大部分时间是在调试代码。由于模板的全局变量用混了，而自己又忘了。，，等西安邀请赛还有四省赛结束之后，该冷静反思下尝试拜托模板了

错误   ：1、k用错，题目的k和模板的k用混;

2、还是二分的C()函数,这个事实上跟前一篇《poj
1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津预选题》的C函数写法差点儿相同。可是比那个简单，可是还是调了一会儿。，。開始的时候。没有记录ret，应该记录ret出现过的最大值

3、last>=kk-1才对，由于lcp[i]本身就是两个子串的公共前缀长度

int C(int x)

{

    int ret=0,last=0;

    for(int i=0;i<=n;i++)

    {

        if(lcp[i]>=x)ret++;

        else

        {

            last=max(last,ret);

            ret=0;

        }

    }

    if(last>=kk-1)return 1;

    else return 0;

}

上代码：

#include <cstdio>

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

const int MAXN = 20200;

int rk[MAXN],sa[MAXN],s[MAXN],tmp[MAXN],lcp[MAXN],n,k,kk;

bool cmpSa(int i,int j)

{

    if(rk[i] != rk[j])return rk[i]<rk[j];

    else

    {

        int ri = i+k<=n?rk[i+k]:-1;

        int rj = j+k<=n?rk[j+k]:-1;

        return ri<rj;

    }

}

void consa()

{

    for(int i=0;i<=n;i++)

        sa[i]=i,rk[i]=i<n?s[i]:-1;

    for(k=1;k<=n;k*=2)

    {

        sort(sa,sa+n+1,cmpSa);

        tmp[sa[0]]=0;

        for(int i=1;i<=n;i++)

        {

            tmp[sa[i]]=tmp[sa[i-1]]+(cmpSa(sa[i-1],sa[i])?1:0);

        }

        for(int i=0;i<=n;i++)

            rk[i]=tmp[i];

    }

}

void construct_lcp()

{

    //n=strlen(s);

    for(int i=0; i<=n; i++)rk[sa[i]]=i;

    int h=0;

    lcp[0]=0;

    for(int i=0;i<n;i++)

    {

        int j=sa[rk[i]-1];

        if(h>0)h--;

        for(; j+h<n && i+h<n; h++)

        {

            if(s[j+h]!=s[i+h])break;

        }

        lcp[rk[i]-1]=h;

    }

}

int C(int x)

{

    int ret=0,last=0;

    for(int i=0;i<=n;i++)

    {

        if(lcp[i]>=x)ret++;

        else

        {

            last=max(last,ret);

            ret=0;

        }

    }

    if(last>=kk-1)return 1;

    else return 0;

}

int main()

{

    //freopen("poj 3261.txt","r",stdin);

    while(scanf("%d%d",&n,&kk)!=EOF)

    {

        for(int i=0;i<n;i++)

            scanf("%d",&s[i]);

        s[n]=-1;

        consa();

        construct_lcp();

        int d=0,up=n+1,mid;

        while(up>d+1)

        {

            mid=(d+up)/2;

            if(C(mid))d=mid;

            else up=mid;

        }

        printf("%d\n",d);

    }

    return 0;

}