用C语言写KMP算法

在C语言中，Knuth-Morris-Pratt (KMP) 算法是一种用于字符串匹配的经典算法，它通过预处理模式串，避免了在每次比较时都回溯的情况，提高了搜索效率。下面是KMP算法的基本步骤：

1. **创建部分匹配表（Partial Match Table, P）**: 根据模式串构建P数组，P[i]表示模式串中前i个字符到失败的位置的距离。初始值P[0]=0，P[i] = j（j < i）意味着如果第一个字符匹配失败，我们只需要跳过j个字符继续搜索。

2. **主循环**:
- 比较输入串和模式串的第一个字符。如果相等，则继续下一位；
- 如果不等，查看P[i]是否存在，即在模式串之前是否已经遇到过当前字符的位置。如果存在，说明当前位置匹配失败，从上次失败的位置开始继续搜索；如果不存在，说明需要从头开始尝试移动模式串。

以下是简单的C语言实现：

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

void compute_lps(char pattern[], int lps[], int len) {
    int index = 0, j = 1;
    while (j < len) {
        if (pattern[j] == pattern[index]) {
            lps[j] = ++index;
            j++;
        } else {
            if (index != 0)
                index = lps[index - 1];
            else {
                lps[j] = 0;
                j++;
            }
        }
    }
}

int kmp_search(char text[], char pattern[]) {
    int m = strlen(pattern);
    int n = strlen(text);
    int lps[m];
    compute_lps(pattern, lps, m);

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

    return -1;
}

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