KMP 模式匹配算法：从零到能自己写

说明：下面内容已按你的要求做过两轮自检，确保包含

1. KMP 的具体实现思路
2. 图表式演示
3. 现实比喻
4. C / Python / Java 三份对照代码
5. 适合算法小白理解的讲解方式

---

1. 先说结论：KMP 到底解决了什么问题？

我们要做的是：

• 在文本串 text 中查找模式串 pattern
• 找到第一次出现的位置

普通暴力匹配的问题

暴力匹配遇到失配时，会把模式串往右挪一格，然后文本串很多字符会被重复比较。

你可以把它想成：

你在找一本书里的某个关键词，已经看了前 5 个字都对上了，结果第 6 个字错了。
暴力算法会“退回去重来”，而 KMP 会说：
“前面已经确认的部分，没必要再看一遍，我直接跳到下一个最有希望的位置。”

---

2. KMP 的核心思想：利用“前缀 = 后缀”的信息

KMP 的灵魂在于一个数组：

• lps
• 也常被叫做 next
• 全称理解成：Longest Prefix Suffix

解释一下什么叫“前缀”和“后缀”

假设模式串是：

ABABCABAA

对于某一段子串，比如 ABABA：

• 前缀：A, AB, ABA, ABAB
• 后缀：A, BA, ABA, BABA

如果某个前缀和后缀相同，就说明这段字符串内部存在“可复用结构”。

---

3. 先用图表演示 lps 是怎么来的

我们用这个模式串：

ABABCABAA

对应下标和 lps 表如下：

下标 i	字符	以 pat[0..i] 结尾的最长相同前后缀长度 lps[i]
0	A	0
1	B	0
2	A	1
3	B	2
4	C	0
5	A	1
6	B	2
7	A	3
8	A	1

所以最终：

pattern = A B A B C A B A A
lps     = 0 0 1 2 0 1 2 3 1

---

4. lps 是怎么“跳”的？实时演示一下

假设我们已经匹配到了：

已匹配部分：ABAB

此时模式串下一位要比的是 C，但文本串对应位置是 A，发生失配。

失配前

text   : ... A B A B A ...
pattern:     A B A B C ...
                   ↑
                这里失配

前 4 个字符 ABAB 里面：

• 前缀：AB
• 后缀：AB

它们相同，所以我们不用把模式串整体右移 4 格重来。

而是直接跳到：

j = lps[4 - 1] = lps[3] = 2

也就是说：

• 已经确认的 AB 还能继续用
• 只从模式串第 3 个字符重新对齐

这就是 KMP 的精髓

文本串指针不回头，模式串指针按 lps 跳转。

---

5. 一个很形象的现实比喻

把模式串想成“印章图案”，把文本串想成“纸上的一长串图案”。

• 暴力匹配：印章盖歪了，就把印章抬起来，回到原点重盖
• KMP：印章盖歪了，会先看已经盖上的那部分有没有“重复结构”
  • 如果有，就直接把印章移动到最合适的位置继续盖
  • 不会把已经确认过的内容重新核对

这就是为什么 KMP 能做到：

• 时间复杂度：O(n + m)
• n 是文本串长度
• m 是模式串长度

---

6. KMP 的完整实现思路

KMP 分两步：

第一步：构建 lps

规则：

lps[i] 表示 pattern[0..i] 中，最长的“真前缀”和“真后缀”相等的长度

---

第二步：正式匹配

两个指针：

• i：指向文本串
• j：指向模式串

规则：

1. text[i] == pattern[j]

   • i++
   • j++

2. 如果 j == pattern.length()

   • 说明匹配成功
   • 返回起始位置 i - j

3. 如果失配：

   • j > 0：j = lps[j - 1]
   • j == 0：i++

---

7. C 语言版本

代码

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

void build_lps(const char *pat, int *lps) {
    int m = (int)strlen(pat);
    int len = 0;      // 当前最长前后缀长度
    lps[0] = 0;       // 第一个字符一定是 0

    for (int i = 1; i < m; ) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmp_search(const char *text, const char *pat) {
    int n = (int)strlen(text);
    int m = (int)strlen(pat);

    if (m == 0) return 0;

    int *lps = (int *)malloc(sizeof(int) * m);
    if (lps == NULL) return -1;

    build_lps(pat, lps);

    int i = 0;  // text 指针
    int j = 0;  // pat 指针

    while (i < n) {
        if (text[i] == pat[j]) {
            i++;
            j++;

            if (j == m) {
                free(lps);
                return i - j;  // 找到第一次匹配的位置
            }
        } else {
            if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    free(lps);
    return -1;
}

int main() {
    const char *text = "BBC ABCDAB ABCDABCDABDE";
    const char *pat = "ABCDABD";

    int pos = kmp_search(text, pat);
    printf("match position = %d\n", pos);

    return 0;
}

C 语言版本重点说明

1）build_lps

它负责把模式串自己“分析一遍”，找出每个位置的最长前后缀长度。

2）kmp_search

它负责真正匹配。

3）为什么 j = lps[j - 1]？

因为当前已经匹配了 j 个字符，失配时要看：

• 已匹配的这段里，能不能找到一个“可复用的前缀”
• lps[j - 1] 就是最优回退位置

---

8. Python 语言版本

代码

def build_lps(pat: str):
    m = len(pat)
    lps = [0] * m
    length = 0  # 当前最长前后缀长度
    i = 1

    while i < m:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length > 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    return lps


def kmp_search(text: str, pat: str):
    if not pat:
        return 0

    n, m = len(text), len(pat)
    lps = build_lps(pat)

    i = 0  # text 指针
    j = 0  # pat 指针

    while i < n:
        if text[i] == pat[j]:
            i += 1
            j += 1

            if j == m:
                return i - j
        else:
            if j > 0:
                j = lps[j - 1]
            else:
                i += 1

    return -1


if __name__ == "__main__":
    text = "BBC ABCDAB ABCDABCDABDE"
    pat = "ABCDABD"
    print(kmp_search(text, pat))

Python 版本重点说明

Python 写起来最简洁，适合学习算法逻辑。

你要特别记住这两句

j = lps[j - 1]
i += 1

它们体现了 KMP 的两个特点：

• 模式串回退
• 文本串不回退

这就是 KMP 的效率来源。

---

9. Java 语言版本

代码

public class KMP {

    public static int[] buildLps(String pat) {
        int m = pat.length();
        int[] lps = new int[m];
        int length = 0; // 当前最长前后缀长度
        int i = 1;

        while (i < m) {
            if (pat.charAt(i) == pat.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length > 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

    public static int kmpSearch(String text, String pat) {
        if (pat.length() == 0) return 0;

        int n = text.length();
        int m = pat.length();
        int[] lps = buildLps(pat);

        int i = 0; // text 指针
        int j = 0; // pat 指针

        while (i < n) {
            if (text.charAt(i) == pat.charAt(j)) {
                i++;
                j++;

                if (j == m) {
                    return i - j;
                }
            } else {
                if (j > 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        String text = "BBC ABCDAB ABCDABCDABDE";
        String pat = "ABCDABD";

        System.out.println(kmpSearch(text, pat));
    }
}

Java 版本重点说明

Java 版本和 Python/C 的核心逻辑完全一样，只是：

• 字符访问方式用 charAt
• lps 用 int[]
• 适合写成类方法，方便封装进工程项目

---

10. 三种语言对比总结

语言	优点	注意点
C	贴近底层，最能体现指针/数组本质	需要手动管理内存
Python	最简洁，最适合初学者理解算法	注意边界条件
Java	工程化强，适合企业开发场景	代码比 Python 稍长

---

11. 你真正需要记住的 3 句话

第一句

KMP 是“利用已知信息避免重复比较”的算法。

第二句

lps 表示模式串前缀和后缀的最长公共长度。

第三句

文本串不回头，模式串按 lps 跳转。

---

12. 最后给你一个极简版心法

你可以把 KMP 背成这个流程：

1. 先给模式串做“体检”——算 lps
2. 匹配时：
   • 相等：两个指针一起走
   • 失配：
     • j > 0，j = lps[j - 1]
     • j == 0，i++
3. 一旦 j == m，说明找到答案

---