字符串的KMP算法 C语言

KMP（Knuth-Pratt）算法是一种用于字符串匹配的高效算法，尤其适合处理长文本搜索短模式的情况。在C语言中，KMP算法的核心在于构建一个部分匹配表（也称作失配函数或最长公共前后缀表）。这个表存储了模式串前缀和前缀所对应的最大不相交字符数。

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

1. **构造部分匹配表**：
- 初始化表，对于每个位置i（从1到模式串长度减一），如果模式串的前i个字符和前i-1个字符相同，失配函数h[i] = h[i-1]；否则，h[i]等于第一个使模式串第i+1个字符和前h[i]+1位置不同的位置。

2. **匹配过程**：
- 当主串和模式串比较时，如果当前字符匹配，则继续向后移动；如果不匹配，查看失配函数h。如果主串当前位置-j（j是模式串当前字符的位置）之前的字符和模式串相同，说明有部分匹配，跳过这j个字符继续对比；若不满足条件，直接尝试下一个字符。

3. **匹配结果**：
- 如果找到整个模式串，则返回成功；如果没有找到，最后返回失败的位置，即主串中最右边的那个位置，可以从该位置开始继续搜索。

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

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

// KMP表的构建
int getFailFunc(char* pattern) {
    int n = strlen(pattern), fail[n];
    for (int i = 1; i < n; ++i) {
        while (fail[i - 1] > 0 && pattern[i] != pattern[fail[i - 1]])
            fail[i] = fail[fail[i - 1]];
        if (pattern[i] == pattern[fail[i - 1]])
            fail[i]++;
    }
    return fail;
}

// KMP匹配
int kmpMatch(char* text, char* pattern) {
    int n = strlen(text), m = strlen(pattern);
    int fail = getFailFunc(pattern);
    for (int i = 0, j = 0; i < n; ++i) {
        if (text[i] == pattern[j])
            ++j;
        else if (j > 0)
            j = fail[j - 1];
        else
            ++i;
        if (j == m)
            return i - m + 1;
    }
    return -1;
}

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