11
1 2 3 5 4 1 2 3 5 4 1
22
1 2 3 2 1 2 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0

输出：
5
7

跪求大神帮忙看一下这个有bug的ac代码...
蒟蒻感激不尽...
#include <iostream>
#include <cstdio>
#define MAXN 500005
using namespace std;

int n, num[MAXN];
int sa[MAXN], Rank[MAXN], height[MAXN], cnt[MAXN];
int tmpa[MAXN], tmpb[MAXN], temp[MAXN];
int l, r, mid;

bool cmp(int num[],int a,int b,int len)
{return num[a]==num[b]&&num[a+len]==num[b+len];}

void work(int n,int m)
{
	int *r=tmpa, *pos=tmpb;
	for(int i=0;i<m;++i)cnt[i]=0;
	for(int i=0;i<n;++i)++cnt[r[i]=num[i]];
	for(int i=1;i<m;++i)cnt[i]+=cnt[i-1];
	for(int i=n-1;i>=0;--i)sa[--cnt[r[i]]]=i;

	for(int len=1, tmp=0;tmp<n;m=tmp, len*=2)
	{
		tmp=0;
		for(int i=n-len;i<n;++i)pos[tmp++]=i;
		for(int i=0;i<n;++i)if(sa[i]>=len)pos[tmp++]=sa[i]-len;

		for(int i=0;i<n;++i)temp[i]=r[pos[i]];
		for(int i=0;i<m;++i)cnt[i]=0;
		for(int i=0;i<n;++i)++cnt[temp[i]];
		for(int i=1;i<m;++i)cnt[i]+=cnt[i-1];
		for(int i=n-1;i>=0;--i)sa[--cnt[temp[i]]]=pos[i];

		swap(r,pos);
		r[sa[0]]=0, tmp=1;
		for(int i=1;i<n;++i)
			r[sa[i]]=cmp(pos,sa[i],sa[i-1],len)?tmp-1:tmp++;
	}
}

void calh(int n)
{
	for(int i=1;i<=n;++i)Rank[sa[i]]=i;
	for(int i=0, k=0, j;i<n;height[Rank[i++]]=k)
		for(k?--k:0, j=sa[Rank[i]-1];num[i+k]==num[j+k];++k);
}

bool check(int mid)
{
    int i=1, b, e;
    while(i<=n)
    {
        while(i<=n&&height[i]<mid) i ++;
        if(i>n) break;
		b=e=sa[i-1];
		while(i<=n&&height[i]>=mid)
		{
			b=min(b,sa[i]), e=max(e,sa[i]);
			++i;
		}
        if(e-b>=mid)return 1;
    }
    return 0;
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;++i)scanf("%d",&num[i]);
        if(n<10)
        {
            puts("0");
            continue;
        }
		--n;
		for(int i=0;i<n;++i)
			num[i]=num[i+1]-num[i]+89;
        num[n]=0;
        work(n+1,180);
        calh(n);
        l=0, r=n;
        while(l<r)
        {
            mid=(l+r+1)/2;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        if(l<4)puts("0");
        else printf("%d\n",l+1);
    }
    return 0;
}

• Re:提供一组数据 (71) zhangjun03402 2016-01-30 16:46:17
• Re:你的数据是错的吧= = (28) hzy9819 2016-02-02 20:06:31