扩展KMP算法(Extend KMP)
扩展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<=k<=i-1，并满足k+A[k]最大
所以T[k]--T[k+A[k]-1]=T[0]--T[A[k]-1]，推出T[i]--T[k+A[k]-1]=T[i-k]--T[A[k]-1]
令L=A[i-k]，若L+i-1<k+A[k]-1，由A是最长公共前缀知A[i]=L，否则，向后匹配，知道字符串失配
并相应更新k
时间复杂度为线性O(m+n)
while(1+j<strlen(T)&&T[0+j]==T[1+j])
j = j + 1;
A[1]=j;
int k=1;
for(int i=2; i<strlen(T); i++)
{
int Len = k + A[k] - 1,L = A[i-k];
if( L < Len - i + 1 )
A[i] = L;
else
{
j = max(0,Len -i +1);
while(i+j<strlen(T)&&T[i+j] == T[0+j])
j = j + 1;
A[i] = j,k = i;
}
}
j = 0;
while(j<strlen(S)&&j<strlen(T)&&T[0+j]==S[0+j])
j = j + 1;
B[0] = j,k = 0;
for(int i=1; i<strlen(S); i++)
{
int Len = k + B[k] - 1,L = A[i-k];
if( L < Len - i + 1 )
B[i] = L;
else
{
j = max(0,Len -i +1);
while(i+j<strlen(S)&&j<strlen(T)&&S[i+j] == T[0+j])
j = j + 1;
B[i] = j,k = i;
}
}
ps:普通的next是到这个结尾的，能和模式串匹配的长度，扩展kmp是以这个开头的能匹配的最大长度
pss:然后我简单比较了下kmp和扩展kmp http://www.isnowfy.com/kmp-and-extend-kmp/
相关文章
- 由于要使用mikoomi mongodb plugin插件，所以需要php对mongodb的扩展支持，默认通过源安装的php并没有mongodb的扩展支持，具体可以通过php -m|grep mongo 验证 。这里就结...2016-11-25
- 安装curl扩展支持https是非常的重要现在许多的网站都使用了https了，下面我们来看一篇关于PHP安装curl扩展支持https例子吧。 问题： 线上运行的lamp服务器，默认yu...2016-11-25
- PHP是一种解释型的语言，对于用户而言，我们精心的控制内存意味着easier prototyping和更少的崩溃！当我们深入到内核之后，所有的安全防线都已经被越过，最终还是要依赖于真正有责任心的软件工程师来保证系统的稳定运行。1、线...2015-11-08
- 这篇文章主要介绍了浅谈Vue开发人员的7个最好的VSCode扩展，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-01-20
- 一、下载pthreads扩展下载地址：http://windows.php.net/downloads/pecl/releases/pthreads二、判断PHP是ts还是nts版通过phpinfo(); 查看其中的 Thread Safety 项，这个项目就是查看是否是线程安全，如果是：enabled，一般来说...2015-11-24
- 这篇文章主要介绍了Redis集群水平扩展、集群中添加以及删除节点的操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-25
- mcrypt 是 php 里面重要的加密支持扩展库，Linux环境下默认是没开启的，在某些功能时，我们需要安装mcrypt扩展才能正常访问，本文就来讲讲如何完全安装这个模块。 如果你...2016-11-25
- pcntl中的php必须要安装pcntl才可以实现多线程了，在网上找到许多的关于pcntl安装教程，下面整理了一篇比较完整的关于php pcntl安装与使用方法。 pcntl中php实现多进...2016-11-25
- 扩展就是向一个已有的类、结构体或枚举类型添加新功能。下面这篇文章主要给大家介绍了关于Swift中限定扩展的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面来一起看看吧。...2020-06-30
- 一、列表/封面模板变量说明：（栏目页或专题页中使用）(一)、当前栏目ID或专题ID：$GLOBALS[navclassid]通过这个变量可以输出这个栏目id的所有数据（如：select * from phome_enewsclas...2016-01-27
- OPcache 通过将 PHP 脚本预编译的字节码存储到共享内存中来提升 PHP 的性能， 存储预编译字节码的好处就是 省去了每次加载和解析 PHP 脚本的开销。PHP 5.5.0 及后续版...2016-11-25
- PHP 作为一个 Web 开发语言，相对来说，命令行程序并不是它的主战场。所以很多年轻的 PHP 开发者可能连命令行脚本都没有写过，更别提交互式的命令操作了。而今天，我们带来的这个扩展就是针对 PHP 的交互式命令行操作的...2021-05-18
PHP中加速、缓存扩展的区别和作用详解(eAccelerator、memcached、xcache、APC )
这篇文章主要介绍了PHP中eAccelerator、memcached、xcache、APC 4个加速、缓存扩展的区别的相关资料,非常不错，具有参考借鉴价值，需要的朋友可以参考下...2016-07-25- MAMP Pro是一款适用于Mac操作系统的软件。MAMP PRO是专业级版本的经典本地服务器环境的os x软件,下面我们来看MAMP PRO安装PHP扩展的方法，具体如下。 这几天因为需...2016-11-25
Linux完整安装ffmpeg及ffmpeg的PHP扩展详情步骤
FFmpeg在Linux平台下开发，但它同样也可以在其它操作系统环境中编译运行，包括Windows、Mac OS X等。本文我们将介绍在Linux下安装ffmpeg及ffmpeg的PHP扩展的详情步骤，还有...2016-11-25- 这篇文章主要介绍了C#、ASP.NET通用扩展工具类之TypeParse,使用了此类,类型转换方便多了,本文直接给出实现代码和使用方法,需要的朋友可以参考下...2020-06-25
php怎么安装sockets扩展？linux下开启php的sockets扩展支持实例
下个相同版本的php源码，进行编译安装，再按照上面步骤搞，生成的so。copy到rpm装的那个，修改php.ini进行扩展就行了。下文有安装的详细过程，大家可以参考一下。 下个相同...2017-07-06安装PHP扩展时解压官方 tgz 文件后没有configure文件无法进行配置编译的问题
这篇文章主要介绍了安装PHP扩展时解压官方 tgz 文件后没有configure文件无法进行配置编译的问题,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友参考下吧...2020-08-27- PDO MySQL模块在安装php环境时默认是没有安装了，如果我们要使用PDO MySQL需要在php.ini配置文件中开启PDO MySQL模块功能即可，具体我来给大家介绍一下配置方法。 ...2016-11-25
- PHP是现在很多人都在学习、使用的，今天文章要给大家介绍的是在IIS下安装PHP扩展的方法，还不知道怎么做的下面一起来看看。 很多网上的文章在介绍IIS下安装PHP的时候...2017-07-06