【C语言】深入理解KMP算法及C语言实现

一、KMP算法简介

 KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，由Donald Knuth、James H. Morris和 Vaughan Pratt共同发明。KMP算法的核心思想是当一次字符比较失败时，利用已经得到的部分匹配信息，将模式字符串向右滑动一段距离后继续比较，从而避免从头开始匹配，提高匹配效率。

二、KMP算法原理

1. 前缀和后缀
   KMP算法中，我们关心模式字符串的前缀和后缀。对于模式字符串P，长度为m，我们定义P的前缀为P[0…i]（0 <= i < m），后缀为P[j…m-1]（0 <= j < m）。如果前缀和后缀相等，我们称这个前缀和后缀为P的一个border。
2. 部分匹配表（Partial Match Table，PMT）
   KMP算法通过计算模式字符串的一个特殊数组——部分匹配表（PMT），来存储每个位置之前（包括当前位置）的字符串的最长border长度。这个数组也被称为next数组。PMT的计算过程如下：
   （1）初始化PMT数组，令PMT[0] = -1，PMT[1] = 0。
   （2）遍历模式字符串P，对于每个位置i（1 < i < m），找到P[0…i-1]的最长border长度，记为k。如果P[k] == P[i]，则PMT[i] = k + 1；否则，继续寻找更短的border，直到找到或k = -1。
3. KMP匹配过程
   KMP匹配过程如下：
   （1）初始化两个指针i和j，分别指向主字符串S和模式字符串P的起始位置。
   （2）遍历主字符串S，对于每个位置i，进行如下操作：
   a. 如果P[j] == S[i]，则i和j分别指向下一个位置，继续比较。
   b. 如果P[j] != S[i]，则利用PMT数组，将j移动到PMT[j]的位置，继续比较。
   c. 如果j移动到模式字符串的起始位置，则i指向下一个位置。
   （3）如果j指向模式字符串的末尾，说明匹配成功，返回匹配的起始位置；否则，匹配失败，返回-1。

三、C语言实现

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

// 计算部分匹配表（PMT）
void computePMT(char *P, int *PMT) {
    int m = strlen(P); // 模式串的长度
    PMT[0] = -1; // PMT数组的第一个元素设为-1
    PMT[1] = 0; // PMT数组的第二个元素设为0
    int k = 0; // 初始化k为0，用于PMT的计算

    // 计算PMT数组
    for (int i = 2; i < m; i++) {
        // 如果当前字符不匹配，并且k不为0，则回退k的位置
        while (k > 0 && P[k] != P[i - 1]) {
            k = PMT[k];
        }
        // 如果当前字符匹配，则k增加1
        if (P[k] == P[i - 1]) {
            k++;
        }
        PMT[i] = k;
    }
}

// KMP搜索算法
int KMP(char *S, char *P) {
    int n = strlen(S); // 主串的长度
    int m = strlen(P); // 模式串的长度
    int *PMT = (int *)malloc(m * sizeof(int)); // 动态分配PMT数组的空间
    computePMT(P, PMT); // 计算PMT数组

    int i = 0, j = 0; // 初始化i和j，分别用于主串和模式串的索引
    // 遍历主串S
    while (i < n) {
        // 如果j为-1或当前字符匹配，则继续匹配下一个字符
        if (j == -1 || S[i] == P[j]) {
            i++;
            j++;
        } else {
            // 如果字符不匹配，则根据PMT数组回退j的位置
            j = PMT[j];
        }
        // 如果j等于模式串的长度，则找到了匹配
        if (j == m) {
            free(PMT); // 释放PMT数组的空间
            return i - j; // 返回匹配的起始索引
        }
    }
    free(PMT); // 释放PMT数组的空间
    return -1; // 如果没有找到匹配，则返回-1
}

int main() {
    char S[] = "ababcabcafgghrfthrhrthrtjtyjcbab"; // 主串
    char P[] = "rhrthrtj"; // 模式串
    int index = KMP(S, P); // 使用KMP算法搜索模式串在主串中的位置

    // 输出结果
    if (index != -1) {
        printf("Pattern found at index %d\n", index);
    } else {
        printf("Pattern not found\n");
    }
    return 0;
}

运行结果：

四、总结

KMP算法是一种高效的字符串匹配算法，通过计算模式字符串的部分匹配表（PMT），在匹配过程中利用已匹配的信息，避免了不必要的重复比较，提高了匹配效率。本文通过C语言实现KMP算法，帮助读者更好地理解KMP算法的原理和实现过程。