BA01-KMP算法¶

算法介绍¶

KMP (Knuth-Morris-Pratt) 算法是一种改进的字符串匹配算法，用于在一个文本串中查找模式串的所有出现位置。相比朴素的字符串匹配算法，KMP通过预处理模式串来避免不必要的字符比较，从而提高匹配效率。

核心思想¶

当发生字符不匹配时，利用已匹配部分的信息，确定模式串应该向右滑动多少位，而不是简单地逐位移动。

完整实现代码¶

C
/**
 * 构造next数组（部分匹配表）
 * @param pattern 模式串
 * @param next    next数组，存储每个位置的最长相等前后缀长度
 * @param len     模式串长度
 */
void buildNext(char* pattern, int* next, int len) {
    // next[0] = 0，因为单个字符没有真前后缀
    next[0] = 0;
    int prefix = 0;  // 前缀末尾位置（同时也是当前最长相等前后缀的长度）

    // 从第二个字符开始计算next值
    for (int suffix = 1; suffix < len; suffix++) {
        // 当前后缀不匹配时，回退到前一个位置的next值继续比较
        while (prefix > 0 && pattern[prefix] != pattern[suffix]) {
            prefix = next[prefix - 1];
        }

        // 如果当前字符匹配，前缀长度加1
        if (pattern[prefix] == pattern[suffix]) {
            prefix++;
        }

        // 记录当前位置的最长相等前后缀长度
        next[suffix] = prefix;
    }
}

/**
 * KMP字符串匹配算法
 * @param text    文本串
 * @param pattern 模式串
 * @return        第一次匹配成功的位置，-1表示未找到
 */
int kmpSearch(char* text, char* pattern) {
    int textLen = strlen(text);
    int patternLen = strlen(pattern);

    // 特殊情况处理
    if (patternLen == 0) return 0;
    if (textLen < patternLen) return -1;

    // 构造next数组
    int next[patternLen];
    buildNext(pattern, next, patternLen);

    int patternIndex = 0;  // 模式串当前匹配位置

    // 遍历文本串进行匹配
    for (int textIndex = 0; textIndex < textLen; textIndex++) {
        // 当字符不匹配时，根据next数组调整模式串位置
        while (patternIndex > 0 && text[textIndex] != pattern[patternIndex]) {
            patternIndex = next[patternIndex - 1];
        }

        // 字符匹配成功，模式串指针前移
        if (text[textIndex] == pattern[patternIndex]) {
            patternIndex++;
        }

        // 完全匹配成功
        if (patternIndex == patternLen) {
            return textIndex - patternLen + 1;  // 返回匹配起始位置
        }
    }

    return -1;  // 未找到匹配
}

复杂度分析¶

时间复杂度¶

预处理阶段（buildNext）: O(m)，其中m是模式串长度
匹配阶段: O(n)，其中n是文本串长度
总体时间复杂度: O(n + m)

空间复杂度¶

next数组: O(m)
总体空间复杂度: O(m)

关键要点记忆¶

next数组含义: 每个位置记录该位置前子串的最长相等前后缀长度
核心优化: 不匹配时利用已匹配信息，避免重复比较
两个阶段: 预处理next数组 + 实际匹配过程
时间优势: 相比朴素算法的O(n×m)，KMP达到O(n+m)

这个实现简洁易懂，注释详细，便于理解和记忆KMP算法的核心思想。