k m p算法的C语言代码实现

kmp算法（Knuth-Morris-Pratt 算法），也称为失配缓存算法，用于在文本串中高效地查找模式串。它通过预先计算部分匹配表（Partial Match Table, PMT），避免了每次比较都从头开始。

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

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

// 功能：构建PMT表
void get_PMT(char pattern[], int PMT[])
{
    int len = strlen(pattern), i = 0, j = -1;
    while (i < len) {
        if (j == -1 || pattern[i] == pattern[j])
            i++, j++;
        else
            j = PMT[j];
        PMT[i] = j;
    }
}

// 主函数：KMP搜索模式
int KMP_search(char text[], char pattern[])
{
    int len_text = strlen(text), len_pattern = strlen(pattern);
    int i = 0, j = 0;
    while (i < len_text && j < len_pattern) {
        if (pattern[j] == text[i])
            j++;
        else if (j != 0)
            j = PMT[j - 1];
        else
            i++;
    }
    // 如果找到匹配，则返回起始索引，否则返回-1
    return j == len_pattern ? i - len_pattern : -1;
}

int main()
{
    char text[] = "ABABCABAB";
    char pattern[] = "ABCAB";
    int PMT[25]; // 为了演示，这里假设模式长度不超过25
    get_PMT(pattern, PMT);

    int result = KMP_search(text, pattern);
    if (result == -1)
        printf("Pattern not found.\n");
    else
        printf("Pattern found at index %d.\n", result);

    return 0;
}

在这个例子中，`get_PMT`函数构建PMT表，`KMP_search`函数使用PMT进行搜索。如果模式在文本中找到，会返回第一个匹配的位置；否则返回-1。