KMP算法

以下是KMP算法的核心原理及C语言实现详解，结合算法流程、代码示例和应用场景展开：

一、KMP算法核心原理

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，通过预处理模式串生成前缀表（next数组），利用已匹配信息跳过不必要的比较，将时间复杂度优化至O(n+m)（n为主串长度，m为模式串长度）。

1. 前缀表（next数组）

• 定义：next[i]表示模式串前i个字符构成的子串中，最长相等前缀和后缀的长度。 • 例如模式串"ABABCABAB"的前缀表为[0,0,1,2,0,1,2,3,4]。 • 作用：当字符匹配失败时，根据next数组确定模式串指针应回退的位置，避免主串指针回溯。

2. 算法优势

• 减少重复比较：暴力算法在匹配失败时主串指针回溯，而KMP算法仅移动模式串指针，主串指针不回溯。 • 关键操作：通过前缀表实现“模式串跳跃”，例如主串"aabaabaafa"与模式串"aabaaf"匹配时，跳过无效的起始位置对比。

二、算法实现步骤

1. 构建next数组

实现逻辑：

初始化双指针i=1（后缀末尾）、j=0（前缀末尾），next[0] = 0。
遍历模式串，若pattern[i] == pattern[j]，则j++并更新next[i] = j。
若不等，j回退至next[j-1]，直到找到匹配或j=0。

C语言代码：

void getNext(char* pattern, int* next) {
    int m = strlen(pattern);
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1]; // 回溯至前一个匹配位置
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
}

2. KMP匹配过程

实现逻辑：

初始化主串指针i=0，模式串指针j=0。
遍历主串，若字符匹配则两指针同时后移。
若匹配失败且j>0，模式串指针回退至next[j-1]；否则主串指针后移。

C语言代码：

int kmp(char* text, char* pattern) {
    int n = strlen(text), m = strlen(pattern);
    if (m == 0) return 0; // 空模式串直接匹配成功
    int* next = (int*)malloc(m * sizeof(int));
    getNext(pattern, next);
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1]; // 根据next数组回退
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) { // 完全匹配
            free(next);
            return i - m + 1; // 返回起始位置
        }
    }
    free(next);
    return -1; // 未找到
}

三、完整示例与测试

1. 示例代码

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

// 上述getNext和kmp函数在此处插入

int main() {
    char text[] = "aabaabaafa";
    char pattern[] = "aabaaf";
    int pos = kmp(text, pattern);
    if (pos != -1) {
        printf("匹配成功，起始位置：%d\n", pos); // 输出：匹配成功，起始位置：3
    } else {
        printf("未找到模式串\n");
    }
    return 0;
}

2. 运行说明

• 输入：主串"aabaabaafa"，模式串"aabaaf"。 • 输出：匹配位置为3，验证了算法正确性。

四、应用场景

文本编辑器：快速查找关键字或替换字符串。
生物信息学：DNA序列比对时高效定位子序列。
数据压缩：LZ77等算法中用于查找重复字符串模式。

五、算法优化

• 改进next数组：若pattern[i] == pattern[next[i]]，可进一步缩短回溯路径，例如模式串"aaaaaab"优化后减少冗余比较。 • 空间优化：动态计算next数组，避免预分配内存。

通过合理利用前缀表和指针跳跃，KMP算法在字符串匹配场景中展现出显著性能优势。如需深入理解递推公式或边界条件，可参考代码注释及文献。