求出子串(模式串)的next,利用kmp算法实验模式与主串的匹配算法。 要求:由键盘输入主串及子串的值,(1)输出子串的next值(注:next的初始值为:next[1]=0)。(2)输出子串在主串中首次出现的位置。C语言描述
时间: 2024-02-09 18:08:32 浏览: 70
好的,我会根据您的要求给出C语言实现KMP算法的代码,以便您更好地理解该算法的实现过程。
```c
#include <stdio.h>
#include <string.h>
void get_next(const char *p, int *next) {
int n = strlen(p);
int i = 0, j = -1;
next[0] = -1;
while (i < n) {
if (j == -1 || p[i] == p[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
int kmp_match(const char *s, const char *p) {
int m = strlen(s);
int n = strlen(p);
int i = 0, j = 0;
int next[n];
get_next(p, next);
while (i < m && j < n) {
if (j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == n) {
return i - n;
}
return -1;
}
int main() {
char s[100], p[100];
printf("请输入主串:");
scanf("%s", s);
printf("请输入子串:");
scanf("%s", p);
int next[strlen(p)];
get_next(p, next);
printf("子串的next值为:");
for (int i = 0; i < strlen(p); ++i) {
printf("%d ", next[i]);
}
printf("\n");
int pos = kmp_match(s, p);
if (pos == -1) {
printf("子串在主串中不存在\n");
} else {
printf("子串在主串中首次出现的位置为:%d\n", pos);
}
return 0;
}
```
在这段代码中,我们首先输入了主串和子串的值。然后,我们定义了一个next数组,用来存储子串中每个位置前面最长公共前后缀的长度。接着,我们调用了get_next函数,该函数用来计算子串的next数组。最后,我们调用了kmp_match函数,该函数用来实现KMP算法的匹配过程,并返回子串在主串中首次出现的位置(如果存在的话)。最后,我们输出了子串的next值和子串在主串中首次出现的位置。
希望这段代码能够对您有所帮助!
阅读全文