当前位置:  编程技术>c/c++/嵌入式

扩展KMP算法(Extend KMP)

    来源: 互联网  发布时间:2014-10-27

    本文导语:  扩展kmp既是求模式串和主串的每一个后缀的最长公共前缀 即令s[i]表示主串中以第i个位置为起始的后缀,则B[i]表示s[i]和模式串的最长公共前缀 显然KMP是求s[i]=模式串长度的情况,所以,扩展KMP是对KMP的拓展 像求KMP的next数组一...

扩展kmp既是求模式串和主串的每一个后缀的最长公共前缀

即令s[i]表示主串中以第i个位置为起始的后缀,则B[i]表示s[i]和模式串的最长公共前缀

显然KMP是求s[i]=模式串长度的情况,所以,扩展KMP是对KMP的拓展

像求KMP的next数组一样,我们先求A[i],表示模式串的后缀和模式串的最长公共前缀

然后再利用A[i]求出B[i]
说明一下A的求法,B同理
现在我们要求A[i],且A[1]---A[i-1]已经求出,设k,且1


    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • jQuery.extend()、jQuery.fn.extend()扩展方法示例详解
  • Jquery中扩展方法extend使用技巧
  • php安装完成后如何添加mysql扩展
  • 对chrome os的panelize扩展的一点困惑。。(就是那个能打开多个窗口的扩展)
  • CentOS下PHP安装完成后继续安装GD扩展库
  • android 获取文件的扩展名和去掉文件扩展名的小例子
  • linux bash shell命令:文本搜索工具grep中用于egrep和 grep -E的元字符扩展集
  • 请教:什么叫扩展字符集,什么又是不扩展阿?
  • 扩展jQuery对象时如何扩展成员变量具体怎么实现
  • 安装Red lnuix9.0的问题,两块硬盘,一块分成一个dos分区,三个dos扩展分区,安装win2000,另一块40G硬盘分成一个dos分区,两个dos扩展分
  • Linux下的文件类型有几种?扩展名分别是什么?可执行文件有扩展名吗,若有的话是什么?
  • 文件的扩展属性问题
  • 扩展逻辑卷,在线急急急。。。
  • PHP 扩展模块 PECL
  • 安装linux时,能否将linux swap分区划在扩展分区中?
  • Symbian图像处理扩展库 NokiaCV
  • 请问用VI命令建立的文件扩展名是什么?
  • PHP的开源扩展 WinBinder
  • jQuery Mobile 图表扩展 JQMCharts
  • 代码覆盖率统计工具gcov的扩展 lcov
  • OpenCV的扩展库 ImageNets
  • 中文分词PHP扩展 MFSOU
  • jquery easyui表单重置扩展思路


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3