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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

后缀数组初级  

2014-04-23 22:04:13|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近几天poj做到了后缀数组的题,于是就去学了以下。由于本人目前的理解能力欠佳,只自学了求rank的算法,还未学高级的LCP、后缀树等等。首先看了nowcow的后缀数组就已经基本懂了,再看了一下09年罗穗骞论文便大概会写了。他写得rank模板十分短小精炼,效率也高,也容易理解。直接贴下代码:
void da(int *r,int *sa,int n,int m) 
//r是字符串,sa是“排第几的是谁”,n是r的长度或者说是排名大小的上限,m是字符串的大小上限 
//用数组指针的作用等会介绍。 
{
     int i,j,p,*x=wa,*y=wb,*t;//x、y数组分别相当于排名和第二关键字的排序。 
     for(i=0;i<m;i++) ws[i]=0;//清空桶排表 
     for(i=0;i<n;i++) ws[x[i]=r[i]]++;//相同个数累加 ,x相当于rank 
     for(i=1;i<m;i++) ws[i]+=ws[i-1];//枚举m,累加ws的值就是对应的排名 
     for(i=n-1;i>=0;--i) sa[--ws[x[i]]]=i;//倒着枚举排名n,范围是0---n-1; 
     for(j=1,p=1;p<n;j*=2,m=p)//开始用倍增合并了 ,m=p,p<n皆为优化
     {
        for(p=0,i=n-j;i<n;i++) y[p++]=i;//后面几位不够的应该用0补充。y记录的值是位置。下标是排名
//由于sa一定已经有序,第二关键字的排序直接可以得出。         
        for(i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;//注意此时y就已经完成。    
        for(i=0;i<m;i++) ws[i]=0;
        for(i=0;i<n;i++) ws[x[y[i]]]++;//枚举排名,对于第二关键字i排名所在位置的第一
//关键字进行相同原理桶排。 
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[x[y[i]]]]=y[i]; 
        for(t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1;i<n;i++)//更新排名rank,由sa可以得出。 指针的威力
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;//注意!在sa中即使是同一个字符串排名也是
//不一样的,而在x(即rank)中必须要相同的。 
     }
}
  评论这张
 
阅读(5147)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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