c语言代码1、应用BF算法求子串"JING"在主串"BEIJING"中的位置,测试起始位置分别为1和5的情况; 2、应用KMP算法求子串"abaabcac"在主串"acabaabaabcacaabc"中的位置,测试起始位置分别为1,10的情况,并写出子串的next[]值和nextval[]的值; 菜单选项为:0、退出;1、BF算法实现;2、KMP算法实现。
时间: 2024-03-13 15:48:10 浏览: 30
好的,以下是C语言代码实现:
1. BF算法实现:
```c
#include <stdio.h>
#include <string.h>
int BF(char *s, char *p, int pos) {
int i = pos, j = 0;
while (i < strlen(s) && j < strlen(p)) {
if (s[i] == p[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == strlen(p)) {
return i - strlen(p) + 1;
} else {
return -1;
}
}
int main() {
char s[] = "BEIJING";
char p[] = "JING";
int pos1 = 1, pos2 = 5;
int res1 = BF(s, p, pos1 - 1);
int res2 = BF(s, p, pos2 - 1);
printf("测试起始位置为%d时,子串在主串中的位置为%d\n", pos1, res1);
printf("测试起始位置为%d时,子串在主串中的位置为%d\n", pos2, res2);
return 0;
}
```
2. KMP算法实现:
```c
#include <stdio.h>
#include <string.h>
void getNext(char *p, int next[], int nextval[]) {
int i = 0, j = -1;
next[0] = -1;
nextval[0] = -1;
while (i < strlen(p)) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
if (p[i] != p[j]) {
nextval[i] = j;
} else {
nextval[i] = nextval[j];
}
} else {
j = next[j];
}
}
}
int KMP(char *s, char *p, int pos, int next[], int nextval[]) {
int i = pos, j = 0;
while (i < strlen(s) && j < strlen(p)) {
if (j == -1 || s[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == strlen(p)) {
return i - strlen(p) + 1;
} else {
return -1;
}
}
int main() {
char s[] = "acabaabaabcacaabc";
char p[] = "abaabcac";
int pos1 = 1, pos2 = 10;
int next[strlen(p)], nextval[strlen(p)];
getNext(p, next, nextval);
int res1 = KMP(s, p, pos1 - 1, next, nextval);
int res2 = KMP(s, p, pos2 - 1, next, nextval);
printf("测试起始位置为%d时,子串在主串中的位置为%d\n", pos1, res1);
printf("测试起始位置为%d时,子串在主串中的位置为%d\n", pos2, res2);
printf("子串的next[]值为:");
for (int i = 0; i < strlen(p); i++) {
printf("%d ", next[i]);
}
printf("\n子串的nextval[]值为:");
for (int i = 0; i < strlen(p); i++) {
printf("%d ", nextval[i]);
}
printf("\n");
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)