C语言KMP算法

KMP算法（Knuth-Morris-Pratt algorithm）是一种用于字符串匹配的高效算法，它的时间复杂度为O(m+n)，其中m为模式串的长度，n为文本串的长度。KMP算法通过利用模式串中的重复信息，避免了朴素算法中不必要的比较，提高了匹配的效率。

KMP算法的核心思想是使用一个辅助数组next[]，用于存储模式串中每个位置的最长公共前后缀长度。通过利用这些信息，可以在匹配过程中跳过一些不必要的比较，从而提高匹配的效率。

下面是KMP算法的实现代码：

#include <stdio.h>
#include <string.h>

// 构建next数组
void getNext(char* pattern, int* next) {
    int patternLength = strlen(pattern);
    next[0] = -1;
    int i = 0, j = -1;

    while (i < patternLength - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// 使用KMP算法进行字符串匹配
void kmpMatch(char* text, char* pattern) {
    int textLength = strlen(text);
    int patternLength = strlen(pattern);
    int next[patternLength];
    getNext(pattern, next);

    int i = 0, j = 0;
    while (i < textLength) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
            if (j == patternLength) {
                printf("在位置 %d 处找到匹配\n", i - j);
                j = next[j];
            }
        } else {
            j = next[j];
        }
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    kmpMatch(text, pattern);    // 使用KMP算法进行字符串匹配
    return 0;
}

注释和讲解：

1. getNext函数用于构建next数组。初始化next[0]为-1，然后利用两个指针i和j从头开始遍历模式串，根据当前字符是否匹配来更新next数组。如果j为-1或者当前字符匹配成功，则将i和j都向后移动一位，并将next[i]赋值为j。如果当前字符匹配失败，则将j更新为next[j]，即回退到前一个字符的最长公共前后缀长度。
2. kmpMatch函数使用KMP算法进行字符串匹配。首先计算文本串和模式串的长度，然后构建模式串的next数组。使用两个指针i和j分别表示文本串和模式串的索引，在匹配过程中，根据当前字符是否匹配来决定指针的移动。如果匹配成功，则将指针i和j都向后移动一位，如果j等于模式串的长度，则说明找到了匹配，打印匹配的位置，并将j更新为next[j]。如果匹配失败，则将指针j更新为next[j]，即回退到上一个字符的最长公共前后缀长度。
3. 在主函数中，我们定义了文本串和模式串，并调用kmpMatch函数进行字符串匹配。

KMP算法通过利用模式串中的重复信息，在匹配过程中避免了不必要的比较，提高了匹配的效率。通过构建模式串的next数组，可以在匹配失败时快速回退到合适的位置，避免了朴素算法中的大量重复比较。因此，KMP算法在实际应用中具有较高的效率。