C语言中KMP字符串匹配算法详解及实现

KMP算法是一种高效的字符串模式匹配算法，它通过预处理模式串来避免不必要的回溯，从而提高匹配效率。该算法的时间复杂度为O(m+n)，其中m为文本串的长度，n为模式串的长度。

算法的核心在于构建一个next数组，该数组记录了模式串中每个位置的最大相同前后缀长度。具体来说，对于模式串P = “p0p1p2...pn”，如果已知p0 = pk, p1 = pk+1, ..., pi = pk+i，则当pk+i+1匹配失败时，可以直接将模式串向右移动，使pi对齐pk+i的位置，而无需重新检查pi及其之前的字符，因为它们已经匹配成功。同时，为了确保不遗漏任何可能的匹配，需要保证对于“p0...pk+i”不存在更大的i和更小的k使得上述条件成立，否则可能会错误地将模式串右移过长的距离。

对于模式串P的任意字符Pr，存在一个特定的下标k(r)，使得从p0到pk(r)-1与从pr-k(r)到pr-1是Pr之前部分字符串的最长相同前后缀。在匹配过程中，如果Pr和文本串中的某个字符匹配失败，可以直接使用pk(r)与之比较。

下面是KMP算法的C语言实现：

#include 
#include 

#define SRC_LEN 100
#define MDL_LEN 20

// 构建next数组
void makeNext(const char *model, int *next, int len) {
    int index = 0, k = -1;
    next[0] = -1;
    while (index         while (k >= 0 && model[index] != model[k])
            k = next[k];
        index++, k++;
        if (model[index] == model[k])
            next[index] = next[k];
        else
            next[index] = k;
    }
}

// 匹配函数
void match(const char *source, const char *model, int *index) {
    int srcIndex = 0, mdlIndex = 0;
    int srcLen = strlen(source), mdlLen = strlen(model);
    int *next = (int *)malloc(mdlLen * sizeof(int));
    makeNext(model, next, mdlLen);
    while (mdlIndex         if (mdlIndex == -1 || source[srcIndex] == model[mdlIndex]) {
            mdlIndex++, srcIndex++;
        } else {
            mdlIndex = next[mdlIndex];
        }
    }
    if (mdlIndex >= mdlLen)
        *index = srcIndex - mdlLen;
    else
        *index = -1;
}

int main() {
    char source[SRC_LEN], model[MDL_LEN];
    int index;
    printf("请输入源字符串: ");
    fgets(source, SRC_LEN, stdin);
    printf("请输入模式字符串: ");
    fgets(model, MDL_LEN, stdin);
    model[strcspn(model, "\n")] = 0; // 去除输入末尾的换行符
    source[strcspn(source, "\n")] = 0; // 去除输入末尾的换行符
    match(source, model, &index);
    printf("匹配位置: %d\n", index);
    return 0;
}

以上代码实现了KMP算法的基本功能，包括构建next数组和执行匹配过程。用户可以通过输入源字符串和模式字符串来测试算法的正确性和效率。