Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  字符串处理分类

扩展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的最大的匹配长度(最长公共前缀长度)。

继续阅读»

KMP算法

字符串匹配是计算机中经典的问题:在一个很长的主字符串S中查找一个较短的模式串T,如果T在S中有出现,输出首次出现的下标,否则输出-1。
字符串匹配算法很多,本文主要讲解其中的KMP算法。KMP算法是一个高效的线性时间算法,其代码量不大,但理解稍有困难,需要细细体会。
以下所有例子及代码实现中,字符串下标均从0开始!

继续阅读»

我的博客

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

站内搜索

最新评论