Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

你拿去自己拍一下吧

Posted by liyuliang001 at 2009-01-24 16:22:54 on Problem 3261
In Reply To:用后缀数组做的(自己弄了很多测试数数据都没有问题),wa了无数次,哪位牛人帮我看看啊(内有代码),给点测试数据也可以啊!!!! Posted by:qjh817937 at 2008-03-19 10:33:23
#include<cstdio>
typedef int arr[20010];
int n,m,k,i,j,tail,head,ans=0;
arr a,sa,rank,x[2],ssa,st,height;
int q[20010][2];
int fmin(int a,int b){
    if (a<b)return a;return b;
}
int fmax(int a,int b){
    if (a>b)return a;return b;
}
void qsort(int l,int r){
     int i=l,j=r,m=a[sa[(l+r)>>1]];
     while (i<j){
           while (a[sa[i]]<m)i++;
           while (a[sa[j]]>m)j--;
           if (i<=j){
              int x=sa[i];sa[i]=sa[j];sa[j]=x;
              i++;j--;
           }
     }
     if (i<r)qsort(i,r);
     if (l<j)qsort(l,j);
}
void sort(int d,int m){
     int i;
     for (i=0;i<=m;i++)st[i]=0;
     for (i=1;i<=n;i++)ssa[i]=sa[i];
     for (i=1;i<=n;i++)st[x[d][sa[i]]]++;
     for (i=1;i<=m;i++)st[i]+=st[i-1];
     for (i=n;i>=1;i--)sa[st[x[d][ssa[i]]]--]=ssa[i];
}
void calcheight(){
     int i,k=0;
     for (i=1;i<=n;i++){
         if (k>0)k--;
         for (;a[i+k]==a[sa[rank[i]-1]+k];k++);
         height[rank[i]]=k;
     }
}
int main(){
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;i++)scanf("%d",&a[i]);
    a[n+1]=-1;
    for (i=1;i<=n;i++)sa[i]=i;
    sa[0]=n+1;
    qsort(1,n);
    for (i=1;i<=n;i++)rank[sa[i]]=rank[sa[i-1]]+(a[sa[i]]!=a[sa[i-1]]);
    for (i=1;1<<i<=n<<1;i++){
        for (j=1;j<=n;j++) x[0][j]=rank[j];
        for (j=1;j<=n;j++) x[1][j]=rank[fmin(j+(1<<i>>1),n+1)];
        if (rank[sa[n]]>m)m=rank[sa[n]];
        sort(1,m);
        sort(0,m);
        for (j=1;j<=n;j++) rank[sa[j]]=rank[sa[j-1]]+(x[0][sa[j]]!=x[0][sa[j-1]]||x[1][sa[j]]!=x[1][sa[j-1]]);
    }
    calcheight();
    k--;
    head=1;tail=0;
    for (i=1;i<k;i++){
        while (head<=tail&&q[tail][0]>=height[i])tail--;
        q[++tail][0]=height[i];
        q[tail][1]=i;
    }
    for (i=k;i<=n;i++){
        if (head<=tail&&i-q[head][1]>=k)head++;
        while (head<=tail&&q[tail][0]>=height[i])tail--;
        q[++tail][0]=height[i];
        q[tail][1]=i;
        if (q[head][0]>ans){
           ans=q[head][0];
        }
    }
    printf("%d\n",ans);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator