扩展KMP算法

扩展KMP的应用：

给出模板串S和串T，长度分别为Slen和Tlen，要求在线性时间内，对于每个S[i]（0<=i

最长公共前缀长度，记为extend[i]（或者说，extend[i]为满足S[i..i+z-1]==T[0..z-1]的最大的z值）。

扩展KMP可以用来解决很多字符串问题，如求一个字符串的最长回文子串和最长重复子串。

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4333

题意：给一个数字，每一次把它的最后一位拿到最前面，一直那样下去，分别求形成的数字小于，等于和大于原来数的个数。

例如：134可以形成134，341，413三个数，所以分别是1，1，1。

分析：

由于长度为len的字符串形成题目要求的串的个数为len，那么我们可以把原来的两个串T连接起来形成字符串S，然后找S的每

个后缀的前len个元素即可。

这里主要是如何比较的问题，对于字符串的比较，我们可以先求出他们的最长公共前缀长度，然后只需要比较一次就可以知道结果了。那么最长公共前缀怎么求，由于这里是一个串T与另一个串S，来求S的所有后缀与T的最长公共前缀长度，所以用扩展

KMP。如果extend[i]>=len，就说明与原来的相等了，否则如果S[i+extend[i]]

于。

#include 
#include 
#define N 500010int next[N];
int nextval[N];
int extend[N];char S[N];
char T[N];void GetNext(char *T)
{int a=0;int Tlen=strlen(T);next[0]=Tlen;while(a=p){int j=(p-k+1)>0? p-k+1:0;while(k+j=p){int j=(p-k+1)>0? p-k+1:0;while(k+j=Tlen) ans2++;else if(S[i+extend[i]]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！