kmp算法

62 阅读 0 评论 41 点赞

我是靠谱客的博主醉熏帆布鞋，最近开发中收集的这篇文章主要介绍kmp算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

方法一

next[0]为-1

内容理解

https://blog.csdn.net/x__1998/article/details/79951598

https://blog.csdn.net/yutianzuijin/article/details/11954939

推荐看第一篇的算法分析，next[]的长度应是模式串的长度+1,才能保证不越界


int KMP(char * t, char * p)
{
int i = 0;
int j = 0;
while (i < strlen(t) && j < strlen(p))
{
if (j == -1 || t[i] == p[j])
{
i++;
j++;
}
else
j = next[j];//比如第一篇里的ababababca
// abababca
//手算：i=6,j=6，哦吼，不一样，next[i]为模式串0~i-1位的最长公共子串，有
//m=4，abab,那么要从哪里开始比较起来，j=m(即第5个开始）
if (j == strlen(p))
return i - j;
else
return -1;
}
void getNext(char * p, int * next)
{
next[0] = -1;
int i = 0, j = -1;
while (i < strlen(p))
{
if (j == -1 || p[i] == p[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];如abaabcac，next[]{-1,0,-1,1,1,2,0,1};//咋算呢，
//next[0]是-1，没啥意义，next[k]，0-k-1最长公共子串的个数，不信算一哈，再跑一会程序验证
}
}
}
------------------------------------------------------------------------------
https://blog.csdn.net/czw8528/article/details/23935153
getNextval
void getnextval(char p[])
{
nextval[0]=-1;
int i=0,j=-1,lenp=strlen(p);
while(i!=lenp-1)
{
if(j==-1||p[i]==p[j])
{
++i;
++j;
if(p[i]!=p[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}

当p[i]==p[j]时，必然有next[i+1]=next[i]+1，则有nextval[i]=nextval[next[i]]。

方法二，next[0] = 0

c++实现

/***严蔚敏版的数据结构***/
/***字符串匹配算法***/
/**这个只是把下标换成从1开始罢了**/
#include<cstring>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255
//用户可在255以内定义最长串长
typedef char SString[MAXSTRLEN+1];
//0号单元存放串的长度
Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
int i;
if (strlen(chars) > MAXSTRLEN)
return ERROR;
else {
T[0] = strlen(chars);
for (i = 1; i <= T[0]; i++)
T[i] = *(chars + i - 1);//傻眼了吧，*char表示的是指针char指向的字符,chars++，表示指针后移
return OK;
}
}
//算法4.3　计算next函数值
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next
int i = 1, j = 0;
next[1] = 0;
while (i < T[0])
if (j == 0 || T[i] == T[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}//get_next
//算法4.2　KMP算法
int Index_KMP(SString S, SString T, int pos, int next[])
{
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
//其中，T非空，1≤pos≤StrLength(S)
int i = pos, j = 1;
while (i <= S[0] && j <= T[0])
if (j == 0 || S[i] == T[j]) // 继续比较后继字
{
++i;
++j;
}
else
j = next[j]; // 模式串向右移动
if (j > T[0]) // 匹配成功
return i - T[0];
else
return 0;
}//Index_KMP
int main()
{
SString S;
StrAssign(S,"aaabbaba") ;
SString T;
StrAssign(T,"abb") ;
int *p = new int[T[0]+1]; // 生成T的next数组
get_next(T,p);
cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配n";
return 0;
}

手算nextval[]

令 nextval[0] = -1。从 nextval[1] 开始，如果某位(字符)与它 next 值指向的位(字符)相同，则该位的 nextval 值就是指向位的 nextval 值(nextval[i] = nextval[ next[i] ])；如果不同，则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。

赋char[]与char *的区别

https://blog.csdn.net/w417950004/article/details/78614455

https://blog.csdn.net/u012611878/article/details/78291036