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

z55250825

一只蒟蒻

 
 
 

日志

 
 

扩展KMP   

2013-11-01 01:41:10|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
纯自己看的,总结一下自己刚刚看所了解的,首先是扩展kmp的用途,它用于求字符串S的所有后缀关于模板T的最长公共前缀(LCP)(莫名奇妙地YY比较下它和后缀数组啥关系),我们用ext[i]表示之,那么扩展KMP可以在O(lenT+lenS)的时间求出ext[].
按像咱一样的弱菜来用朴素算法做 我们每次比较实际上把很多不必要的工作重复了,像KMP一样,这个重复的工作量是可以像KMP一样解决的,比如对于S[i]aaaaa失配,我们就可以知道S[i+1]的长度至少为4,这些信息实际上就表现为S[i]与S[i+1]的最长公共前缀,那么我们可以将S与T的LCP转化成相邻后缀的LCP,而相邻后缀的LCP即它们与SLCP的较小值,则问题由T转化成求S后缀。
我们对于自身LCP计算,考虑一个普通情景,即我们已经求出了ext[1],ext[2],……,ext[i-1],设ext[k]+k-1为所有1< jiextjj-extii-SiSLCPexti>
1)S[1……ext[k]]=S[k……k+ext[k]-11](LCP定义)
2)i>k
3)S[1+i-k……ext[k]]=S[i……k+ext[k]-1]
4)设ext[i+1-k]=L,则有
S[1……L]=S[i+1-k……i+1-k+L-1]
5)由3),4),设k+ext[k]-1=p
则S[1
  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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