c语言kmp算法实现代码并提供案例

KMP（Knuth-Pratt）算法是一种高效的字符串匹配算法，它通过构建部分匹配表（也称为失配函数），避免了在搜索过程中多次回溯。以下是C语言中KMP算法的一个基本实现：

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

// 定义部分匹配表辅助函数
void compute_lps(char* pattern, int lps[], int len) {
    int i = 0, j = -1;
    while (i < len) {
        if (i > j || pattern[i] == pattern[j]) {
            i++;
            j++;
            lps[i] = j;
        } else {
            j = lps[j];
        }
    }
}

// KMP匹配函数
int kmp_search(char* text, char* pattern) {
    int m = strlen(pattern);
    int n = strlen(text);
    int lps[m];
    compute_lps(pattern, lps, m);

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (pattern[j] == text[i])
            j++;
        else if (j != 0)
            j = lps[j - 1];
        else
            i++;
    }

    if (j == m)
        return i - m; // 如果找到匹配，返回起始位置
    else
        return -1; // 没有找到匹配
}

int main() {
    char text[] = "ABABCABADC";
    char pattern[] = "ABC";
    int position = kmp_search(text, pattern);
    if (position != -1)
        printf("Pattern found at index %d\n", position);
    else
        printf("Pattern not found in the text.\n");
    return 0;
}

在这个例子中，`text` 是要查找的目标文本，`pattern` 是需要在文本中查找的模式串。`compute_lps` 函数计算了部分匹配表，`kmp_search` 根据这个表在文本中查找模式。如果找到匹配，`kmp_search` 返回匹配的开始位置；否则返回 `-1`。