kmp模式匹配算法c语言

KMP（Knuth-Pratt）算法是一种用于字符串匹配的经典算法，它通过预处理模式串，避免了回溯操作，提高了搜索效率。在C语言中，KMP算法的工作原理主要包括以下几个步骤：

1. **构造部分匹配表**（Partial Match Table, PMT）：PMT用于存储模式串中每个位置失败前的最大相等字符数。对于每个位置i，如果它的前缀和子串从0到i-1匹配，则P[i] = P[j]，否则P[i] = j - i。

2. **匹配过程**：给定主串和模式串，从头开始逐个比较。如果当前字符匹配，移动到下一个字符；如果不匹配，查找PMT找到最长的非空前缀和当前字符的最长公共前后缀长度，然后从模式串当前位置加上这个长度继续比较。

3. **优化**：如果在某个时刻发现主串和模式串的当前位置不匹配，直接利用PMT跳过部分已匹配的部分，而不是回溯整个模式串。

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

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

// KMP表构造函数
void compute_lps(char* pattern, int lps[]) {
    int len = strlen(pattern);
    lps[0] = 0;
    int i = 1;
    
    while (i < len) {
        if (pattern[i] == pattern[lps[i]]) {
            lps[i + 1] = lps[i] + 1;
            i++;
        } else {
            if (lps[i] != 0) {
                lps[i + 1] = lps[i];
            } else {
                lps[i + 1] = 0;
            }
            i++;
        }
    }
}

// KMP匹配函数
int kmp_search(char* text, char* pattern) {
    int m = strlen(text), n = strlen(pattern);
    int lps[n], j = 0;
    compute_lps(pattern, lps);

    for (int i = 0; i < m; i++) {
        while (j > 0 && pattern[j] != text[i]) {
            j = lps[j - 1];
        }
        if (pattern[j] == text[i]) {
            j++;
        }

        // 如果j等于n，说明找到了一个匹配
        if (j == n) {
            return i - n + 1;
        }
    }
    return -1;
}

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