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

 
 
 

日志

 
 

【转载】后缀数组 height 数组的构建  

2014-05-07 08:05:48|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一开始问了一些神犇,然后回答都是说后缀数组很简单,为何我却感觉很复杂呢,于是决定还是先搬运点东西到这里来

height[i]LCP(i-1,i),即height[i]代表第i小的后缀与第i-1小的后缀的LCP,则求LCP(i,j)就等于求height[i+1]~height[j]之间的RMQ,套用RMQ算法就可以了,复杂度是预处理O(nlogn),查询O(1)

然后height的求法要用到另一个数组:令h[i]=height[Rank[i]],即h[i]表示Suffix(i)height值(同时height[i]就表示Suffix(SA[i])height值),则有height[i]=h[SA[i]]
然后h[i]有个性质:

·         h[i] >= h[i-1]-1

用这个性质我们在计算h[i]的时候进行后缀比较时只需从第h[i-1]位起比较,从而总的比较的复杂度是O(n),也就是说h数组在O(n)的时间内解决了。求出了h数组,根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组,于是可以在O(n)时间内求出height数组,从而整个LCP问题就解决了^_^

然后后缀数组的应用就是利用它的LCP在需要字符串比较时降低复杂度。同时由于后缀数组的有序性可以很方便地使用二分


  评论这张
 
阅读(128)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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