扩展KMP
2013-11-01 01:41:10| 分类：
算法
| 标签：
|举报
|字号大中小 订阅
纯自己看的，总结一下自己刚刚看所了解的，首先是扩展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
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论