C语言数据结构KMP算法介绍

欢迎大家来到IT世界,在知识的湖畔探索吧!

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. 主函数中测试了一个示例。

欢迎大家来到IT世界,在知识的湖畔探索吧!