KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。其时间复杂度为O(m+n)，其中m为主串的长度，n为模式串的长度。理解KMP算法的关键是要理解它使用的“部分匹配表”(partial match table)，该表可以在O(n)的时间内预处理出来，用于帮助寻找匹配失败时应该跳转到的下一个位置。举个例子，假设要在字符串s中查找子串t，算法流程如下： 1.首先需要预处理出t的部分匹配表（next数组）； 2.从s的第一个字符开始依次比较和t对应位置上的字符是否相等； 3.如果相等，则比较下一个字符，直到t中所有字符都匹配成功； 4.如果不相等，则根据next数组跳转到下一个位置，重新开始匹配。下面是KMP算法的代码实现，以查找模式串t在主串s中的所有出现位置为例：```c#include <stdio.h>#include <string.h>/* 计算模式串t的部分匹配表next */void compute_next(char *t, int *next) {    int i, j, len;    len = strlen(t);    next[0] = -1;  /* 第0位设置为-1 */    i = 0, j = -1;    while (i < len) {        if (j == -1 || t[i] == t[j]) {  /* t[i]匹配成功 */            i++;            j++;            next[i] = j;        } else {            j = next[j];  /* t[i]匹配失败，j跳转到next[j] */        }    }}/* 在主串s中查找模式串t */int kmp(char *s, char *t) {    int i, j, slen, tlen, next[100];    slen = strlen(s);    tlen = strlen(t);    compute_next(t, next);  /* 计算t的部分匹配表next */    i = 0, j = 0;    while (i < slen) {        if (j == -1 || s[i] == t[j]) {  /* s[i]匹配成功 */            i++;            j++;        } else {            j = next[j];  /* s[i]匹配失败，j跳转到next[j] */        }        if (j == tlen) {  /* 匹配成功，返回匹配位置 */            printf("found at position %d\n", i - tlen);            j = next[j];  /* 继续查找下一次出现的位置 */        }    }    return 0;}int main() {    char *s = "abacababc", *t = "ababc";    kmp(s, t);    return 0;}```代码注释：1. `compute_next`函数计算模式串t的部分匹配表next，采用的是双指针匹配的方式。2. `kmp`函数中，首先计算出t的部分匹配表next，然后从主串s的第一个字符开始依次比较和t对应位置上的字符是否相等。如果相等，则比较下一个字符，直到t中所有字符都匹配成功；如果不相等，则根据next数组跳转到下一个位置，重新开始匹配。如果匹配成功，则输出匹配位置，并继续查找下一次出现的位置。3. 主函数中测试了一个示例。