使用c语言，通过kmp算法判断目标串是否包含模式串

在C语言中，KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的有效方法，特别适合查找文本串中是否存在某个固定的模式串。KMP算法避免了不必要的比较，提高了搜索效率。下面是基本的步骤：

1. **构建失配函数**（Partial Match Function, PMF）：对于模式串，计算出最长的“良好前缀”和“良好后缀”相等的部分长度数组。这个数组帮助我们在遇到前缀和后缀不匹配的情况时，能够快速跳过部分字符。

2. **初始化**：设置两个指针，i（指向主串的位置）和 j（指向模式串的位置），并开始循环。

3. **匹配过程**：
- 如果 i 和 j 指向的字符相同，i 自增；j 自增；
- 如果 i 指向的字符大于或等于模式串的 j+1 位置的字符，说明当前模式串前面有重复，尝试移动 j 到 PMF 数组里找到合适的偏移量，使得模式串从 j+PMF[j] 开始重新匹配；
- 如果 i 越界而 j 还没到模式串结束，说明主串中不存在该模式串。

4. **检查结果**：当 i 等于模式串的长度时，表示找到了一个匹配；如果 i 小于模式串长度，则继续寻找下一个可能的匹配。

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

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

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

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 (text[i] == pattern[j])
            i++, j++;
        else if (j != 0)
            j = lps[j - 1];
        else
            i++;
    }

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

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