输入两组字符串,第一组S作为主串,第二组T作为模式串,分别使用BF、KMP算法进行模式匹配。c语言
时间: 2024-10-18 13:07:22 浏览: 21
在C语言中,我们可以使用Brute Force (朴素匹配,也叫暴力匹配) 和 Knuth-Morris-Pratt (KMP) 算法来实现两个字符串之间的模式匹配。
**Brute Force (朴素匹配):**
朴素匹配是最基础的匹配方式,对于每一种字符,它会从主串S的第一个位置开始检查,看是否与模式串T相匹配。如果匹配,就继续移动;如果不匹配,就尝试在主串中向右移动一位再进行比较。这种方法的时间复杂度是O(n*m),其中n是主串长度,m是模式串长度,效率较低。
**Knuth-Morris-Pratt (KMP) 算法:**
KMP算法是一种改进的字符串匹配算法,它利用了已知信息(前缀函数)来避免无效的匹配。首先构建模式串T的前缀表,记录每个前缀和下一个位置的关系。然后在主串S中查找,当遇到不匹配的情况时,不是简单地跳过一个字符,而是根据前缀表找到应该跳过的距离。这大大减少了不必要的比较次数,时间复杂度优化到了O(n+m),在处理较长的模式串时更为高效。
以下是使用C语言实现这两种算法的基本结构:
```c
// KMP算法
int* getPrefixTable(char pattern[], int n) {
// 前缀表的构造...
}
void kmpSearch(char text[], char pattern[]) {
int i = 0, j = 0;
while (i < strlen(text)) {
if (text[i] == pattern[j]) {
i++;
j++;
} else if (j != 0) {
// 根据前缀表调整j
j = prefixTable[j - 1];
} else {
i++;
}
if (j == strlen(pattern)) {
// 匹配成功
printf("Pattern found at index %d\n", i - j);
j = 0; // 清空模式串指针
}
}
}
// Brute Force (朴素匹配)
void bruteForceSearch(char text[], char pattern[]) {
for (int i = 0; i <= strlen(text) - strlen(pattern); i++) {
int match = 1;
for (int j = 0; j < strlen(pattern); j++) {
if (text[i + j] != pattern[j]) {
match = 0;
break;
}
}
if (match) {
printf("Pattern found at index %d\n", i);
}
}
}
```
阅读全文