返回目录

公共前后缀：KMP算法的“摸鱼神器”

当你的字符匹配主串和模式串匹配到第100个字符时才发现这个老牧师的***(出题人肯定干过这种事)写了个sz代码，按照暴力匹配的老规矩，主串指针得乖乖退回到第2个字符，模式串从头开始重新比对，相当于前面99个字符的匹配全白干，纯纯无效加班。‌公共前后缀‌就是专门来拯救这场“无效返工”的核心逻辑，堪称字符串匹配界的摸鱼小天才。

1. 概念拆解：什么是公共前后缀？

先给它拆明白：

• ‌前缀‌：就是一个字符串掐掉最后一个字符，从开头能拆出来的所有连续子串。比如“花生米”的前缀就是“花”、“花生”，绝对不能把完整的“花生米”算进去。
• ‌后缀‌：反过来，是掐掉第一个字符，从末尾拆出来的所有连续子串。对应“花生米”的后缀就是“米”、“生米”，同样不能包含完整字符串。
• ‌公共前后缀‌：就是前缀和后缀里“撞号”的那部分。

举个栗子，“花生米”里找不出重合的前缀后缀，它的最长公共前后缀长度就是 0，属于完全没有“复用价值”的字符串。但如果是“ababa”，它的前缀有 a, ab, aba, abab，后缀有 a, ba, aba, baba，其中 a 和 aba 是公共的，最长的就是 aba，长度为3。

2. 核心原理：为什么它能？

别小看这个平平无奇的概念，它就是 ‌KMP算法‌ 能让主串指针“绝不后退”的核心底气。

当匹配半路翻车时，我们根本不用把之前比对过的字符重新跑一遍——因为前面已经匹配成功的那一大段字符串里，藏着一段完全重合的‌公共前后缀‌。这部分内容本来就和主串里的对应字符对上了，直接把模式串指针跳到这段公共前后缀的末尾下一位，就能接着往下比对。

这相当于直接跳过了几百个没必要重复做的步骤，把原本可能 $O(n \times m)$ 的慢动作，拉成了线性级别的丝滑速度。

3. 代码实现逻辑：自己跟自己对“暗号”

放到代码原理里，我们根本不用每次都从头遍历所有子串找公共前后缀，只需要用两个指针在模式串上走一遍就能搞定（通常称为构建 next 数组或 prefix 表）：

1. ‌双指针登场‌：

   • 一个‌后缀指针‌（通常记为 i）往前扫，代表当前正在计算哪个位置的最长公共前后缀。
   • 一个‌前缀指针‌（通常记为 j）专门记录当前最长公共前后缀的长度，同时也指向下一个待匹配的字符位置。

2. ‌匹配成功‌：

   • 如果两个指针指向的字符刚好对上（pattern[i] == pattern[j]），说明最长公共前后缀能再长一格。
   • 操作：j 加 1，记录下当前位置 i 的最长公共前后缀长度为 j，然后两个指针一起往前挪。

3. ‌匹配失败‌：

   • 要是字符对不上，j 不能直接归零，那样太浪费。j 会往回跳，跳到‌上一个更短的公共前后缀的末尾位置‌（即 j = next[j-1]），接着和当前后缀指针 i 对比。
   • 这步回溯的逻辑是：既然长的公共前后缀对不上，那就看看短一点的有没有可能对上，充分利用已知的信息。

4. ‌彻底没戏‌：

   • 直到前缀指针 j 回到起点（j=0）还对不上，就说明当前位置没有公共前后缀，直接把长度记成 0，然后后缀指针 i 继续往前走。

整个过程相当于模式串自己和自己先对了一遍“暗号”，提前把每一步匹配失败后该跳去的位置都记好。后面正式和主串匹配的时候，全程不做半分无用功，主打一个高效摸鱼。

注:以上内容为DeePseek生成

代码演示

void nxt() {
    // 初始化：第一个字符没有前缀和后缀，所以最长公共前后缀长度为0
    nt[0] = 0; 
    
    ans = 0; // 用于记录整个模式串中出现的最大公共前后缀长度（可选功能）
    
    // j 代表“前缀末尾”的位置，同时也代表“当前已匹配的最长公共前后缀长度”
    // 初始时，对于 i=1 的情况，我们假设前一个位置(i-1=0)的最长匹配长度是0
    int j = 0; 
               // 标准写法通常在外层维护 j，或者像下面这样在循环内基于 nt[i-1] 获取初始 j。
               
    // 遍历模式串的每一个位置 i，从第2个字符（下标1）开始，直到最后一个字符
    for (int i = 1; i < n; i++) {
        
        // 【关键步骤1】继承上一位的“遗产”
        // nt[i-1] 记录了 s[0...i-1] 这个子串的最长公共前后缀长度。
        // 这意味着 s[0...j-1] 和 s[i-j...i-1] 是完全一样的。
        // 所以我们尝试接着这个长度往后比，看 s[i] 能不能和 s[j] 对上。
        int j = nt[i - 1]; 
        
        // 【关键步骤2】如果不匹配，就疯狂“回溯”
        // 当 j > 0 说明还有更短的公共前后缀可以尝试；
        // 当 s[i] != s[j] 说明当前长度的前缀后缀接不上了。
        // 这时，我们不能直接清零，而是要跳到“更短一级的公共前后缀”去试试。
        // nt[j-1] 就是 s[0...j-1] 这个前缀串本身的最长公共前后缀长度。
        // 这步操作保证了我们不会漏掉任何可能的匹配机会，同时避免了暴力回退。
        while (j > 0 && s[i] != s[j]) {
            j = nt[j - 1]; 
        }
        
        // 【关键步骤3】如果匹配成功，长度加1
        // 经过上面的回溯，要么 j=0（没得退了），要么 s[i]==s[j]（对上了）。
        // 如果对上了，说明在原来的公共前后缀基础上，又多匹配了一个字符。
        if (s[i] == s[j]) {
            j++; 
        }
        
        // 【关键步骤4】记录结果
        // 现在 j 的值，就是 s[0...i] 这个子串的最长公共前后缀长度。
        nt[i] = j; 
        
        // 更新全局最大值（如果题目需要求整个串的最大对称程度）
        ans = max(ans, j); 
    }
}