KMP算法，全称为Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法，尤其在C语言中，它能够避免不必要的指针回溯，从而提高搜索效率。在传统的字符串匹配算法，如朴素的模式匹配算法中，当模式串（pattern）的某个字符与主串（text）的对应字符不匹配时，需要将模式串的指针回溯至失配位置的前面重新匹配，这导致了效率低下。KMP算法通过预先计算一个“部分匹配表”（next数组），解决了这一问题。
部分匹配表next[]记录了在模式串中，当前字符之前已匹配的最长公共前后缀的长度。当出现不匹配时，我们不再回溯主串，而是直接利用next[]中的信息，使模式串的指针跳过已经匹配的部分，继续与主串进行比较。这显著减少了无效的匹配操作，提高了算法的执行效率。
下面是一个C语言实现KMP算法的例子：
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 101
void get_next(int *next, char *a, int la) {
int i = 1, j = 0;
next[1] = 0;
while (i <= la) {
if (a[i] == a[j] || j == 0) {
j++;
i++;
if (a[i] == a[j])
next[i] = next[j];
else if (j != 0)
j = next[j];
}
}
}
int KMP_search(char *s, char *p, int slen, int plen, int *next) {
int i = 0, j = 0;
while (i < slen && j < plen) {
if (s[i] == p[j])
i++, j++;
else if (j != 0)
j = next[j];
else
i++;
}
if (j == plen)
return i - plen;
else
return -1;
}
int main() {
char text[MAX], pattern[MAX];
int next[MAX], slen, plen;
printf("请输入主串: ");
fgets(text, MAX, stdin);
text[strlen(text) - 1] = '\0'; // 去除末尾换行符
slen = strlen(text);
printf("请输入模式串: ");
fgets(pattern, MAX, stdin);
pattern[strlen(pattern) - 1] = '\0';
plen = strlen(pattern);
get_next(next, pattern, plen);
int index = KMP_search(text, pattern, slen, plen, next);
if (index != -1)
printf("模式串在主串中的位置: %d\n", index);
else
printf("模式串不在主串中\n");
return 0;
}
```
在这个例子中，`get_next()`函数用于计算模式串的next[]数组，`KMP_search()`函数实现了KMP算法的字符串匹配。在`main()`函数中，我们首先获取用户输入的主串和模式串，然后计算next[]数组，最后使用KMP算法查找模式串在主串中的位置。
KMP算法的关键在于预处理部分匹配表next[]，它使得在处理不匹配时能快速跳跃到下一个可能的匹配起点，避免了重复比较。这种优化使得KMP算法在处理大量数据时表现出优越的性能，尤其在模式串较长或者需要多次匹配不同模式串的情况下。
