Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  扩展KMP算法标签

扩展KMP算法

前面介绍过经典的KMP算法,本文继续介绍KMP算法的扩展,即扩展KMP算法:给定一个较长的主字符串S和一个较短的模式串T,用m、n分别表示S和T的长度(即m=|S|,n=|T|),定义extend[i]=S[i..n]与T的最长公共前缀的长度,求extend[i]。
为什么说这是KMP算法的扩展呢?显然,如果在S的某个位置x有extend[x]==n,则可知在S中可以找到T,并且首位置是x,这正是KMP算法要解决的问题。而且,扩展KMP算法能找到S中所有T的匹配,更一般地,可以知道S中以每个字符开始的后缀与T的最大的匹配长度(最长公共前缀长度)。

继续阅读»

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论