独立编写一个程序,实现字符串模式匹配 BF 算法。1在Main函数中调用自己实现BF算法的函数(使用c语言)
时间: 2024-10-11 13:04:37 浏览: 14
在C语言中,我们可以使用广度优先搜索(BFS)算法来实现字符串模式匹配。这种算法通常用于在文本串中查找是否存在某个固定的模式串。下面是一个简单的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义状态数组,记录模式字符的位置
#define MAX_SIZE 100 // 可调整以适应更大的输入
char pattern[MAX_SIZE];
int pattern_pos = 0;
void bfs_search(char text[], int text_len) {
int len = strlen(pattern);
int i, j;
for (i = 0; i <= text_len - len; ++i) { // 搜索范围从0到text_len-len
bool match = true; // 初始化匹配标志为true
for (j = 0; j < len; ++j) {
if (text[i + j] != pattern[j]) {
match = false;
break;
}
}
if (match) { // 找到了匹配
printf("Pattern found at index %d in the text\n", i);
pattern_pos = 0; // 清空模式位置
} else if (pattern_pos == len - 1) { // 如果模式未结束但在当前文本块上找不到,向前移动模式起点
pattern_pos = 0;
} else {
pattern_pos++; // 否则,模式继续下一位
}
}
}
int main() {
char input_text[] = "Hello, World!";
int text_len = sizeof(input_text) / sizeof(input_text[0]);
printf("Enter a pattern to search:\n");
fgets(pattern, sizeof(pattern), stdin); // 输入模式串
// 将fgets读取的换行符移除
pattern[strcspn(pattern, "\n")] = '\0';
bfs_search(input_text, text_len);
return 0;
}
```
在这个示例中,`bfs_search`函数接受一个文本串和其长度作为参数,然后遍历文本,尝试将模式串与每个位置的部分匹配。如果找到匹配,则打印匹配位置,同时更新模式位置以便于接下来的搜索。
阅读全文