kmp算法代码c语言

KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的有效算法。它通过构建部分匹配表（也称作失配函数），避免了回溯过程，提高了搜索效率。以下是简单的C语言实现：

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

// 失配函数，记录前缀到某位置的最大相同字符数
int getPrefixFunction(const char* pattern) {
    int prefix[ strlen(pattern) ];
    int j = -1;
    for (int i = 0; pattern[i]; ++i) {
        while (j != -1 && pattern[j + 1] != pattern[i]) {
            j = prefix[j];
        }
        if (pattern[j + 1] == pattern[i]) {
            ++j;
        }
        prefix[i] = j;
    }
    return prefix;
}

// KMP字符串匹配函数
int kmpSearch(const char* text, const char* pattern) {
    int prefix[] = getPrefixFunction(pattern);
    int i = 0, j = 0;
    while (text[i] != '\0' && pattern[j] != '\0') {
        if (text[i] == pattern[j]) {
            i++, j++;
        } else {
            if (j != 0)
                j = prefix[j - 1];
            else
                i++;
        }
    }
    return (text[i] == pattern[j] ? i - j : -1);
}

int main() {
    const char* text = "ABABDABACDABC";
    const char* pattern = "ABCD";
    int result = kmpSearch(text, pattern);
    if (result == -1)
        printf("Pattern not found.\n");
    else
        printf("Pattern starts at index %d.\n", result);
    return 0;
}

在这个代码中，`getPrefixFunction`函数计算了模式串的前缀函数，而`kmpSearch`函数则根据这个函数进行匹配。当在文本中找到模式串时，返回其起始索引；如果找不到，则返回-1。