KMP 算法 - 前缀函数（笔记）

一、前置知识：前缀函数

1. 定义

对于字符串 str，前缀函数数组 pi 中： pi[i] = 子串 str[0...i] 中，最长相等真前缀与真后缀的长度

• 真前缀：从开头截取，不包含最后一个字符
• 真后缀：从末尾截取，不包含第一个字符
• 核心：找最长的、前后相等的子串

2. 作用

用于 KMP 算法中，匹配失败时快速跳转，避免主串指针回退，提升效率。

---

二、求前缀函数（代码 + 讲解）

完整代码

public static int[] computePrefixFunction(String str) {
    int n = str.length();
    int[] pi = new int[n];         // 前缀函数数组

    // i 从 1 开始，pi[0] 默认是 0（单个字符无前后缀）
    for (int i = 1; i < n; i++) {
        int len = pi[i - 1];       // 继承上一轮最长相等前后缀长度

        // 不匹配就回退
        while (len != 0 && str.charAt(i) != str.charAt(len)) {
            len = pi[len - 1];
        }

        // 匹配成功，长度 +1
        if (str.charAt(i) == str.charAt(len)) {
            len++;
            pi[i] = len;
        }
    }

    return pi;
}

---

逐行逻辑讲解

1. 初始化

   • n：字符串长度
   • pi[]：存储前缀函数结果，默认全 0

2. 循环计算（i 从 1 开始）

   • i：当前要计算的位置
   • len = pi[i-1]：先继承上一轮的最长长度，尝试直接延长

3. 不匹配 → 回退

   while (len != 0 && str.charAt(i) != str.charAt(len)) {
       len = pi[len - 1];
   }

   • 无法延长则不断回退
   • 直到 len=0 或字符匹配

4. 匹配 → 长度+1

   if (str.charAt(i) == str.charAt(len)) {
       len++;
       pi[i] = len;
   }

   • 匹配成功则最长长度 +1
   • 赋值给当前 pi[i]

---

三、执行流程口诀

1. 先继承上一轮长度
2. 不匹配就回退
3. 匹配就加一
4. 赋值给当前位置

---

四、示例

字符串：abcabcabb 前缀函数结果：[0, 0, 0, 1, 2, 3, 4, 5, 0]

---

五、核心意义

前缀函数 = KMP 的跳转表

• 匹配失败时不用从头比
• 直接跳转到最长可匹配位置
• 时间复杂度：O(n)