C语言实现KMP算法：提升字符串匹配效率

KMP算法，全称Knuth-Morris-Pratt字符串查找算法，是一种在文本字符串S内查找字符串模式P的高效算法。KMP算法的核心是前缀函数（或称为部分匹配表），用于在不匹配时将模式字符串相对于文本字符串有效地移动。该算法由Donald Knuth、Vaughan Pratt和James H. Morris共同发明，因此被命名为KMP算法。 在C语言中实现KMP算法，主要涉及到以下几个步骤： 1. 计算部分匹配表（前缀函数）：该表记录了模式串的前缀和后缀的最长共有元素长度。例如，对于模式串ABCDABD，它的部分匹配表为[0, 0, 1, 2, 0, 1, 2]。计算这个表的时间复杂度是O(m)，其中m是模式串的长度。 2. 使用部分匹配表进行搜索：在搜索过程中，如果当前字符不匹配，则根据部分匹配表找到模式串应该滑动到的位置。这部分操作避免了从头开始比较，大大提升了算法效率。 3. 实现匹配函数：该函数接收文本串和模式串，返回模式串在文本串中的所有出现位置或是否出现。 在C语言中，KMP算法的实现会涉及到字符串的遍历、数组操作以及递归或循环结构。 KMP算法的特点是： - 时间复杂度较低，为O(n+m)，其中n是文本串长度，m是模式串长度。 - 空间复杂度为O(m)，主要由部分匹配表决定。 KMP算法可以避免不必要的回溯，因此与朴素的字符串匹配算法相比，具有显著的效率优势。朴素算法在不匹配时，会逐个字符回溯模式串，时间复杂度为O(n*m)。 在具体编码实现上，我们首先定义一个函数用于计算部分匹配表，然后定义主函数用于执行匹配过程。在主函数中，如果遇到不匹配的字符，我们就会根据部分匹配表来决定模式串的移动距离，而不是简单地将模式串向右移动一位。 KMP算法的代码实现如下： ```c #include <stdio.h> #include <string.h> void computeLPSArray(char* pat, int M, int* lps); // KMP算法主体函数 void KMPSearch(char* pat, char* txt) { int M = strlen(pat); int N = strlen(txt); // 创建lps[]，将保存最长前缀后缀长度 int lps[M]; // 计算lps[]数组 computeLPSArray(pat, M, lps); int i = 0; // txt的索引 int j = 0; // pat的索引 while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { printf("找到模式串在索引 %d \n", i - j); j = lps[j - 1]; } // 不匹配情况 else if (i < N && pat[j] != txt[i]) { // 不需要匹配lps[0..lps[j-1]]字符，它们已经匹配了 if (j != 0) j = lps[j - 1]; else i = i + 1; } } } // 计算lps数组的函数 void computeLPSArray(char* pat, int M, int* lps) { int len = 0; // lps的长度 lps[0] = 0; // lps[0]始终为0 // 循环计算lps[i]的值 int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { // (pat[i] != pat[len]) if (len != 0) { len = lps[len - 1]; } else { // 如果len为0 lps[i] = 0; i++; } } } } int main() { char txt[] = "ABABDABACDABABCABAB"; char pat[] = "ABABCABAB"; KMPSearch(pat, txt); return 0; } ``` 在上述代码中，`computeLPSArray` 函数用于计算部分匹配表，`KMPSearch` 函数用于根据部分匹配表执行搜索，最终通过输出来表示模式串在文本串中的所有匹配位置。 KMP算法在多个场景下有着广泛的应用，比如文本编辑器中的查找功能、字符串匹配问题等。掌握KMP算法，对于提高算法和编程能力有着积极的意义。