学KMP的时候(很多算法都是这样)感觉真的就是To talk is easy,show your code。索性把两种KMP以及连续的KMP都写好一遍传上来,已经经过数据集验证正确性,可以放心使用。代码也是尽量比较简洁明了的风格,也方便我和大家复习自用。原理解析的话因为画图解释需要一点时间,有需要的话可以评论区@我,后面可以再找时间写一个详细的解析,不过KMP网上解析的视频也很多了,我看的是左程云左神学的,他讲的是真的很不错。不过代码没有用他的代码,用了这种更为简练的版本(速度肯定是一样快的,而且他那个版本思路要更清晰)。闲话休提,上代码。
'''cpp
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//警告 下面的一些++j,i++等的混合写法,有时候编译器会出错!!
//写开来不会耗费多少时间!!!
//保证安全性!!!!
//求nextVal数组
int *getNextVal(char *s, int length) {
int *next = (int *)malloc (sizeof(int) * (length + 1));
next[0] = -1;
int i = 0, j = -1;
while (i < length) {
if (j == -1 || s[i] == s[j])
next[++i] = ++j;
else
j = next[j];
}
return next;
}
//用nextVal数组实现的KMP,就是next[0]=-1那个
void KMPVal(char s1[], char s2[]) {
int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
int *next = getNextVal(s2, len2);
int i = 0, j = 0;
while (i < len1 && j < len2) {
if (j == -1 || s1[i] == s2[j]) {
j++;
i++;
} else
j = next[j];
}
if (j == len2)
printf("%d", i - j + 1);
else
printf("no finding");
}
//nextVal数组实现的连续KMP
void continueKMPVal(char s1[], char s2[]) {
int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
int *next = getNextVal(s2, len2);
int i = 0, j = 0;
while (i < len1) {
if (j == -1 || s1[i] == s2[j]) {
i++;
j++;
} else
j = next[j];
if (j == len2) {
printf("%d ", i - j + 1);
j = next[j];
}
}
}
//求next数组,next【0】=0那个
int *getNext(char *s, int length) {
int i = 1, j = 0;
int *next = (int *)malloc(sizeof(int) * length);
next[0] = 0;
while (i < length) {
if (s[i] == s[j])
next[i++] = ++j;
else if (j > 0)
j = next[j - 1];
else
next[i++] = 0;
}
return next;
}
//next数组实现的KMP
void KMP(char s1[], char s2[]) {
int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
int *next = getNext(s2, len2);
int i = 0, j = 0;
while (i < len1 && j < len2) {
if (s1[i] == s2[j]) {
i++;
j++;
} else if (j > 0)
j = next[j - 1];
else
i++;
}
if (j == len2)
printf("%d", i - j + 1);
else
printf("no finding");
}
//next数组实现的KMP
void continueKMP(char s1[], char s2[]) {
int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
int *next = getNext(s2, len2);
int i = 0, j = 0;
while (i < len1) {
if (j == -1 || s1[i] == s2[j]) {
i++;
j++;
} else
j = next[j - 1];
if (j == len2) {
printf("%d ", i - j + 1);
j = next[j - 1];
}
}
}
int main() {
char s1[100], s2[100];
gets(s1);
gets(s2);
}
标签:包含,len2,int,s2,s1,next,++,版本,KMP
From: https://blog.csdn.net/clannad551/article/details/143448037