C语言KMP算法

下面是C语言实现KMP算法的示例代码：

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

// 预处理模式串，求出每个前缀的最长公共前后缀长度
void get_next(char* pattern, int* next) {
    int n = strlen(pattern);
    int j = 0, k = -1;
    next[0] = -1;
    while (j < n - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

// KMP算法实现字符串匹配
int kmp_search(char* pattern, char* text) {
    int m = strlen(pattern);
    int n = strlen(text);
    int i = 0, j = 0;
    int next[m];
    get_next(pattern, next);
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == m) {
        return i - j;  // 返回匹配的起始位置
    } else {
        return -1;  // 表示未匹配成功
    }
}

int main() {
    char* text = "ABABABACDABABCABAB";
    char* pattern = "ABABCABAB";
    int pos = kmp_search(pattern, text);
    if (pos != -1) {
        printf("匹配成功，起始位置为：%d\n", pos);
    } else {
        printf("未匹配成功！\n");
    }
    return 0;
}

上述代码中，`get_next()`函数用于预处理模式串，求出每个前缀的最长公共前后缀长度，存储在`next`数组中。`kmp_search()`函数则是实现KMP算法的核心部分，利用已匹配的位置和模式串中的最长公共前后缀长度来计算下一次匹配的位置，直到匹配成功或者结束。在主函数中调用`kmp_search()`函数实现字符串匹配。