个人理解的kmp算法
程序员文章站
2022-07-03 12:42:53
kmp还是挺难上手的,看书加看博客,看了有五六篇才理解,看了大概四个小时。。#include #include #include using namespace std;//next数组本质是模式串中的前缀和后缀的相等数int next[555];//得到next数组的过程也是模式串自身匹配的过程void GetNext(char *p){ int plen=strlen(p);...
kmp还是挺难上手的,看书加看博客,看了有五六篇才理解,看了大概四个小时。。
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
//next数组本质是模式串中的前缀和后缀的相等数
int next[555];
//得到next数组的过程也是模式串自身匹配的过程
void GetNext(char *p)
{
int plen=strlen(p);
next[0]=-1;
//k为前缀,j为后缀
int k=-1;
int j=0;
while(j<plen-1)
{
if(k==-1||p[j]==p[k])
{
k++;
j++;
if(p[j]!=p[k])
next[j]=k;
else next[j]=next[k];
}
else
{
k=next[k];
}
}
}
int kmp(char *s,char *p)
{
int i=0;
int j=0;
int sLen = strlen(s);
int pLen = strlen(p);
while(i<sLen && j < pLen)
{
if(j == -1 || s[i] == p[j])
{
i++;
j++;
}
else//若是字符不匹配
{
//这里相当于将j减去一个j-next[j]
//联想一下那个匹配的图,主串不动,模式串变化,即为模式串相当于主串滑动
//即相当于模式串向右滑动了j-next[j]位
j = next[j];
}
}
if(j == pLen)
return i - j;
else
return -1;
}
int main()
{
char a[555],b[555];
cin>>a>>b;
GetNext(b);
int n=kmp(a,b);
printf("%s",a+n);
return 0;
}
本文地址:https://blog.csdn.net/zhoucheng_123/article/details/107479319
上一篇: 古代没有暖气,古人怎么过冬呢?