注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

USACO 5.5 Hidden Passwords (hidden)  

2009-10-25 17:44:34|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
又是一道后缀树组的题,再次写之,以纪念
恩,dc3果然是个好东西

言归正传,这个题只要把原串复制一遍,加到最后,再在最后面加一个很大的数,然后dc3解决之
#include<cstdio>
    bool compar(int a1,int b1,int a2,int b2){
         return (a1<a2)||(a1==a2&&b1<=b2);
    }
    bool compar(int a1,int b1,int c1,int a2,int b2,int c2){
         return (a1<a2)||(a1==a2&&compar(b1,c1,b2,c2));
    }
    void radix(int n,int k,int a[],int b[],int t[]){
         int c[k+1];
         for(int i=0;i<=k;i++)
           c[i]=0;
         for(int i=0;i<n;i++)
           c[t[a[i]]]++;
         for(int i=0,sum=0;i<=k;i++){
                 int kk=c[i];
                 c[i]=sum;
                 sum+=kk;
         }
         for(int i=0;i<n;i++)
           b[c[t[a[i]]]++]=a[i];
    }
    void aa(int n,int k,int sa[],int t[]){
         int n1=(n+2)/3,n2=n1+n/3,n0=(n+1)/3;
         int sa12[n2+3]; sa12[n2]=sa12[n2+1]=sa12[n2+2]=0;
         int r[n2+3]; r[n2]=r[n2+1]=r[n2+2]=0;
         int sa0[n1];
         int r0[n1];
         for(int i=0,j=0;i<n+n1-n0;i++)
           if(i%3!=0)
             r[j++]=i;
         radix(n2,k,r,sa12,t+2);
         radix(n2,k,sa12,r,t+1);
         radix(n2,k,r,sa12,t);            
         int num=0,c1=-1,c2=-1,c3=-1;
         for(int i=0;i<n2;i++){
           if(t[sa12[i]]!=c1||t[sa12[i]+1]!=c2||t[sa12[i]+2]!=c3){
             c1=t[sa12[i]];
             c2=t[sa12[i]+1];
             c3=t[sa12[i]+2];
             num++;
           }
           if(sa12[i]%3==1) r[sa12[i]/3]=num;
           else r[sa12[i]/3+n1]=num;
         }
         if(num<n2){
           aa(n2,num,sa12,r);
           for(int i=0;i<n2;i++) 
            r[sa12[i]]=i+1;
         }
         else
           for(int i=0;i<n2;i++)
                    sa12[r[i]-1]=i;
         for(int i=0,j=0;i<n2;i++)
           if(sa12[i]<n1)        
              r0[j++]=sa12[i]*3;
         radix(n1,k,r0,sa0,t);
         for(int i=n1-n0,j=0,p=0;p<n;p++){
           #define geti() (sa12[i]<n1? sa12[i]*3+1:(sa12[i]-n1)*3+2)
           int ii=geti();
           int jj=sa0[j];
           if(sa12[i]<n1? compar(t[ii],r[sa12[i]+n1],t[jj],r[jj/3])
                           :compar(t[ii],t[ii+1],r[sa12[i]-n1+1],t[jj],t[jj+1],r[jj/3+n1])){
             i++;
             sa[p]=ii;
             if(i==n2)
               for(p++;j<n1;j++,p++)sa[p]=sa0[j];
           }else{
                 sa[p]=jj;
                 j++;
                 if(j==n1)
                   for(p++;i<n2;i++,p++)sa[p]=geti();
                 }
         }
    }
int main(){
    freopen("hidden.in","r",stdin);
    freopen("hidden.out","w",stdout);
    int n;
    scanf("%d\n",&n);
    int t[2*n+4],sa[2*n+4];
    char c;
    for(int i=0;i<n;i++){
            scanf("%c",&c);
            while(c<'a'||c>'z')
              scanf("%c",&c);
            t[i]=c-'a'+1;
            t[n+i]=c-'a'+1;
    }
    t[2*n]=27;
    t[2*n+1]=t[2*n+2]=t[2*n+3]=0;
    aa(2*n+1,27,sa,t);
    for(int i=0;i<=n;i++)
      if(sa[i]<n){
        printf("%d\n",sa[i]);
        break;
      }
}
  评论这张
 
阅读(369)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018