用C语言写一个基于Boyer-Moore算法的字符串子串查找匹配函数,匹配成功返回0,匹配不成功返回1
时间: 2024-11-06 22:35:49 浏览: 27
好的,下面是一个用C语言实现的基于Boyer-Moore算法的字符串子串查找匹配函数。如果匹配成功返回0,匹配不成功返回1。
```c
#include <stdio.h>
#include <string.h>
// 计算坏字符表
void preprocessBadChar(int *badChar, const char *pattern) {
int m = strlen(pattern);
for (int i = 0; i < 256; i++) {
badChar[i] = -1;
}
for (int i = 0; i < m; i++) {
badChar[(unsigned char)pattern[i]] = i;
}
}
// Boyer-Moore算法实现
int boyerMooreSearch(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
int badChar[256];
// 预处理坏字符表
preprocessBadChar(badChar, pattern);
int shift = 0; // 模式相对于文本的偏移量
while (shift <= (n - m)) {
int j = m - 1;
// 从右向左比较模式和文本
while (j >= 0 && pattern[j] == text[shift + j]) {
j--;
}
// 如果模式完全匹配
if (j < 0) {
return 0; // 匹配成功
} else {
shift += (j - badChar[(unsigned char)text[shift + j]]);
if (shift < 0) {
shift = 0;
}
}
}
return 1; // 匹配不成功
}
int main() {
const char *text = "这是一个测试字符串";
const char *pattern = "测试";
int result = boyerMooreSearch(text, pattern);
if (result == 0) {
printf("匹配成功\n");
} else {
printf("匹配不成功\n");
}
return 0;
}
```
### 代码说明:
1. **预处理坏字符表**:`preprocessBadChar`函数用于生成坏字符表,该表记录了每个字符在模式中最右边出现的位置。
2. **Boyer-Moore搜索**:`boyerMooreSearch`函数实现了Boyer-Moore算法,通过坏字符规则进行模式匹配。如果找到匹配的模式,则返回0;否则返回1。
3. **主函数**:`main`函数中定义了待搜索的文本和模式,并调用`boyerMooreSearch`函数进行匹配,最后输出匹配结果。
这个实现是一个简单的版本,只考虑了坏字符规则。Boyer-Moore算法还可以结合好后缀规则等其他优化策略来提高性能。
阅读全文