请用C语言编程实现串的模式匹配的BF算法。
时间: 2023-12-03 12:05:16 浏览: 85
C语言数据结构之模式匹配字符串定位问题
5星 · 资源好评率100%
好的,下面是C语言代码实现串的模式匹配的BF算法:
```c
#include <stdio.h>
#include <string.h>
int BF(char* s, char* p) {
int i = 0, j = 0;
int len_s = strlen(s);
int len_p = strlen(p);
while (i < len_s && j < len_p) {
if (s[i] == p[j]) {
i++;
j++;
} else {
i = i - j + 1; // 回溯到上次匹配位置的下一个位置
j = 0;
}
}
if (j == len_p) {
return i - j;
} else {
return -1;
}
}
int main() {
char s[] = "hello, world!";
char p[] = "world";
int pos = BF(s, p);
if (pos == -1) {
printf("Not found\n");
} else {
printf("Found at position %d\n", pos);
}
return 0;
}
```
BF算法是一种朴素的串匹配算法,时间复杂度为O(n*m),其中n和m分别为文本串和模式串的长度。算法思路是从文本串的第一个字符开始,依次和模式串的字符进行匹配,如果匹配成功则继续匹配下一个字符,如果匹配失败则回溯到上次匹配位置的下一个位置重新开始匹配。如果最终匹配成功,则返回模式串在文本串中的起始位置,否则返回-1表示未找到。
阅读全文