kmp模式匹配算法用c语言

KMP（Knuth-Pratt）算法是一种用于文本搜索的高效字符串匹配算法。它通过预处理模式串（即要查找的目标串），创建一个失配指针数组（也称为部分匹配表），避免了在每次比较失败时回溯整个模式串的过程。

在C语言中，KMP算法的基本步骤包括：

1. **构建失配指针数组**：对于每个字符，计算从该位置开始的最长公共前缀长度，如果遇到与前面已计算部分相同的前缀，说明当前位置可以不用回溯，继续向后移动；否则，失配指针等于当前失配指针，记录下这个信息。

2. **主匹配循环**：在目标串中逐位与模式串进行比较，当发现不匹配时，利用失配指针决定是从头开始还是跳过一些字符继续比对。

3. **匹配成功或失败**：如果所有字符都匹配完成，则找到一个子串与模式串相等，匹配成功。如果某次不匹配时，按照失配指针调整，然后继续尝试匹配下一个子串。

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

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

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

int KMP_search(char text[], char pattern[]) {
    int m = strlen(pattern), n = strlen(text);
    int lps[m], i, j;

    compute_lps(pattern, lps);

    while (i < n && j < m) {
        if (text[i] == pattern[j])
            i++, j++;
        else {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }

    if (j == m)
        return i - m; // 如果完全匹配，返回匹配起始位置

    return -1; // 没有找到匹配
}

int main() {
    char text[] = "ABABCABCDAB";
    char pattern[] = "ABC";
    printf("Pattern '%s' is found at index %d in the text.\n", pattern, KMP_search(text, pattern));
    return 0;
}