首页 > 程序开发 > 软件开发 > C++ >

poj 3261 后缀数组 找重复出现k次的子串(子串可以重叠)

2014-05-22

做的蛮顺的,1A 但是大部分时间是在调试代码,因为模板的全局变量用混了,而自己又忘了,,,等西安邀请赛还有四省赛结束之后,该冷静反思下尝试拜托模板了 错误 :1、k用错,题目的k和模板的k用混; 2、还是二

做的蛮顺的,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 
#include 
#include 
#include 

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]0)h--;
        for(; j+h=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;id+1)
        {
            mid=(d+up)/2;
            if(C(mid))d=mid;
            else up=mid;
        }
        printf(%d
,d);
    }
    return 0;
}




相关文章
最新文章
热点推荐