KMP算法，全称为Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法。它由Donald Knuth、James H. Morris和Vijay R. Pratt共同发明，旨在解决字符串搜索问题，通过避免重复扫描已匹配的字符，从而提高搜索效率。
KMP算法的基本原理
KMP算法的核心思想是“部分匹配表”（也称为“前缀函数”或“失败函数”）。该算法通过构建一个部分匹配表，用来记录模式串在匹配过程中，一旦发生不匹配时，模式串可以滑动到的位置。
部分匹配表
部分匹配表是由模式串的子串的前缀和后缀的最长相等匹配的长度构成的。例如，对于模式串
ABCDABD
，其部分匹配表为：
ABCDABD -> 0 0 0 0 1 2 3
在这个例子中，第4个字符开始匹配，第5个字符不匹配，但由于部分匹配表的存在，我们知道模式串可以滑动到第3个字符之后，这样可以避免重复检查已经匹配过的字符。
KMP算法步骤
构建部分匹配表。
从主串和模式串的第一个字符开始比较。
如果字符匹配，则继续比较下一个字符。
如果不匹配，则根据部分匹配表，将模式串向右滑动到合适的位置，然后继续比较。
KMP算法的C语言实现
以下是一个简单的KMP算法C语言实现：
#include
#include
void computeLPSArray(char* pat, int M, int* lps) {
int len = 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++;
}
}
}
}
void KMPSearch(char* pat, char* txt) {
int M = strlen(pat);
int N = strlen(txt);
int lps[M];
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern 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;
}
}
}
}
int main() {
char txt[] = "ABABDABACDABABCABAB";
char pat[] = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
KMP算法的实战应用
KMP算法在许多场景下都有广泛的应用，以下是一些例子：
文本编辑器中的搜索功能
：许多文本编辑器都使用KMP算法来快速搜索文本。
生物信息学
：在生物信息学中，KMP算法用于DNA序列的匹配。
数据压缩
：在数据压缩中，KMP算法可以用于查找重复的模式。
KMP算法是一种高效且强大的字符串匹配算法，通过理解其原理和实现，我们可以更好地理解和应用它。