用c语言编写一个KMP字符串匹配代码

在C语言中，KMP算法（Knuth-Morris-Pratt Algorithm）是一种高效的字符串搜索算法，用于在一个文本串中查找指定模式串的所有匹配位置。下面是一个简单的KMP算法的实现示例：

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

// 定义辅助函数，计算部分匹配表
void compute_lps(char pattern[], int lps[], int length) {
    int i = 0, j = -1;
    lps[0] = 0;

    while (i < length) {
        if (pattern[i] == pattern[j + 1]) {
            j++;
            i++;
            lps[i] = j + 1;
        } else {
            if (j != -1)
                j = lps[j];
            else
                i++;
        }
    }
}

// KMP主函数
int kmp_search(char text[], char pattern[]) {
    int len_text = strlen(text);
    int len_pattern = strlen(pattern);
    int lps[len_pattern]; // 部分匹配表
    int index = 0; // 文本指针

    compute_lps(pattern, lps, len_pattern);

    while (index < len_text) {
        if (pattern[index] == text[index])
            index++;

        if (index == len_pattern) {
            printf("Pattern found at position %d in the text\n", index - len_pattern);
            index = lps[index - 1]; // 如果有匹配，从上次失败的位置继续
        } else if (text[index] != pattern[index]) {
            if (index > 0)
                index = lps[index - 1];
            else
                index++;
        }
    }

    return index == len_text; // 返回是否找到全部匹配
}

int main() {
    char text[] = "ABABDABACDABABCAB";
    char pattern[] = "ABCDAB";
    if (!kmp_search(text, pattern)) {
        printf("No match found.\n");
    }
    return 0;
}

在这个例子中，`compute_lps` 函数构建了部分匹配表 `lps`，`kmp_search` 主函数则通过这个表来搜索文本串。如果找到匹配，则返回匹配位置；如果没有找到，则返回`false`。