132 lines
3.6 KiB
Markdown
132 lines
3.6 KiB
Markdown
---
|
||
tags:
|
||
- KMP
|
||
- AI生成
|
||
- C语言
|
||
---
|
||
KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的算法，它能在O(n+m)的时间复杂度内完成字符串的匹配，其中n是主串的长度，m是模式串的长度。这个算法是由Donald Knuth、Vaughan Pratt和Vaughan Morris在1970年共同发明的。
|
||
|
||
KMP算法的主要思想是利用已经匹配过的信息，避免再次从头开始匹配。具体来说，KMP算法在匹配失败后，能够知道模式串中有一部分字符是与主串匹配的，因此不需要重新匹配这些字符。
|
||
|
||
KMP算法的关键在于构造一个“部分匹配表”（也称为“失败函数”或“跳转表”），这个表记录了模式串中每个位置的最长公共前后缀的长度。在匹配过程中，如果发生了匹配失败，就可以根据这个表来确定下一步应该比较的位置，从而避免了不必要的比较。
|
||
|
||
KMP算法的具体实现过程如下：
|
||
|
||
1. 构造部分匹配表。对于模式串中的每个位置i（1≤i≤m），计算以该位置结尾的最长公共前后缀的长度，并将结果存储在部分匹配表的第i个位置。这个计算过程可以通过动态规划来实现。
|
||
|
||
2. 进行字符串匹配。从主串的第一个字符和模式串的第一个字符开始比较，如果相等，则继续比较下一个字符；如果不相等，则根据部分匹配表来确定下一步应该比较的位置。重复这个过程，直到匹配成功或者遍历完整个主串。
|
||
|
||
KMP算法的时间复杂度为O(n+m)，其中n是主串的长度，m是模式串的长度。这个算法在实际应用中非常广泛，特别是在需要频繁进行字符串匹配的场景中，如搜索引擎、文本编辑器等。
|
||
|
||
下面是一个用C语言实现的KMP（Knuth-Morris-Pratt）字符串匹配算法的示例代码。这个示例中，我们实现了KMP算法来在一个主字符串（text）中查找一个模式字符串（pattern）的所有出现位置。
|
||
|
||
```c
|
||
|
||
#include <stdio.h>
|
||
#include <string.h>
|
||
// 函数原型声明
|
||
|
||
void computeLPSArray(char *pat, int M, int *lps);
|
||
void KMPSearch(char *pat, char *txt);
|
||
|
||
int main() {
|
||
char text[] = "ABABDABACDABABCABAB";
|
||
char pattern[] = "ABABCABAB";
|
||
printf("Text: %s\n", text);
|
||
printf("Pattern: %s\n", pattern);
|
||
KMPSearch(pattern, text);
|
||
return 0;
|
||
|
||
}
|
||
|
||
// 计算LPS（最长公共前后缀）数组
|
||
|
||
void computeLPSArray(char *pat, int M, int *lps) {
|
||
|
||
int len = 0; // 最长公共前后缀的长度
|
||
|
||
lps[0] = 0; // lps[0] 总是0
|
||
|
||
int i = 1;
|
||
|
||
while (i < M) {
|
||
|
||
if (pat[i] == pat[len]) {
|
||
|
||
len++;
|
||
|
||
lps[i] = len;
|
||
|
||
i++;
|
||
|
||
}
|
||
else {
|
||
|
||
if (len != 0) {
|
||
|
||
len = lps[len - 1];
|
||
|
||
}
|
||
else {
|
||
|
||
lps[i] = 0;
|
||
|
||
i++;
|
||
|
||
}
|
||
|
||
}
|
||
|
||
}
|
||
|
||
}
|
||
|
||
// KMP字符串匹配算法
|
||
|
||
void KMPSearch(char *pat, char *txt) {
|
||
|
||
int M = strlen(pat);
|
||
|
||
int N = strlen(txt);
|
||
|
||
int lps[M];
|
||
|
||
int j = 0; // 模式串的索引
|
||
|
||
// 计算LPS数组
|
||
|
||
computeLPSArray(pat, M, lps);
|
||
|
||
int i = 0; // 文本串的索引
|
||
|
||
while (i < N) {
|
||
|
||
if (pat[j] == txt[i]) {
|
||
|
||
j++;
|
||
|
||
i++;
|
||
|
||
}
|
||
|
||
if (j == M) {
|
||
printf("Pattern found at index %d \n", i - j);
|
||
j = lps[j - 1];
|
||
}
|
||
else if (i < N && pat[j] != txt[i]) {
|
||
if (j != 0)
|
||
j = lps[j - 1];
|
||
else
|
||
i = i + 1;
|
||
}
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
在这个示例中，`computeLPSArray`函数计算了模式串的最长公共前后缀数组（LPS数组），而`KMPSearch`函数使用这个数组来在文本串中查找模式串。当找到匹配时，它会打印出模式串在主字符串中的起始索引。
|
||
|
||
你可以编译并运行这段代码来测试KMP算法。请确保你的编译器支持C语言标准，并且已经正确设置了编译环境。
|
||
|
||
内容由AI大模型生成，仅供参考
|