C语言实现串匹配中的KMP算法

在C语言中，KMP算法（Knuth-Morris-Pratt 算法）是一种用于高效字符串搜索的算法，尤其适用于在文本中查找特定模式串。它通过预处理模式串构建一个部分匹配表（也叫失配表），避免了每次失败匹配时回溯整个模式串的过程，从而提高了搜索效率。

以下是KMP算法的基本步骤：

1. **创建失配表**：对于模式串，从左到右扫描，如果当前字符和前一个字符相等，则继续；若不相等，记录当前位置之前的已成功匹配的长度，并将这个长度存入失配表。

2. **搜索过程**：对于目标串和模式串，同时遍历。当遇到不匹配时，根据失配表移动目标串的位置，而不是模式串，直到找到一个位置使得目标串的剩余部分可以尝试匹配。

3. **匹配检查**：比较两个字符，如果相等则继续，不相等则根据失配表更新目标串的位置。

4. **返回结果**：如果找到了模式串，返回起始索引；否则，表示未找到。

下面是一个简单的C语言实现KMP算法的例子：

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

// 创建失配表的函数
void computeLPS(char pattern[], int lps[], int len) {
    int i = 0, j = -1;
    while (i < len) {
        if (pattern[i] == pattern[j + 1]) {
            lps[i] = ++j;
            i++;
        } else if (j != -1) {
            j = lps[j];
        } else {
            lps[i] = 0;
            i++;
        }
    }
}

// KMP搜索函数
int kmp_search(char text[], char pattern[]) {
    int m = strlen(pattern);
    int n = strlen(text);
    int lps[m]; // 存储失配信息
    computeLPS(pattern, lps, m);

    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        if (j == m) { // 找到了模式
            return i - j; // 返回匹配的起始位置
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) // 如果不是首次不匹配
                j = lps[j - 1]; // 根据失配表移动
            else
                i++; // 否则直接向后移动
        }
    }
    return -1; // 没有找到
}

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