KMP 算法的核心思想

学习目标

本节学习 KMP 算法的核心思想。

KMP 是经典字符串匹配算法。初学时不必急着记住完整细节，先理解它为什么比暴力匹配更高效：当匹配失败时，KMP 不会把已经匹配过的信息全部丢掉，而是利用模式串自身的结构决定下一步应该移动到哪里。

暴力匹配浪费了什么信息

假设模式串前面一部分已经匹配成功，但在后面某个字符失败。

暴力匹配会放弃当前起点，然后把模式串整体向后移动一位，并从模式串开头重新比较。

问题在于：前面已经比较过的字符里，其实包含了有用信息。如果模式串自身有重复前缀和后缀，就可以利用这些信息避免从头开始。

KMP 的核心就是：失败时不回退主串指针，而是调整模式串指针。

前缀和后缀

理解 KMP 需要先理解前缀和后缀。

对于字符串 abab：

前缀可以是 a、ab、aba。
后缀可以是 b、ab、bab。

如果某个前缀和某个后缀相同，就说明模式串内部存在可复用的结构。

例如 abab 的最长相同前后缀是 ab。

KMP 会为模式串的每个位置计算这种信息，形成前缀表，也常称为 next 数组或 lps 数组。

lps 数组的含义

lps 可以理解为 longest proper prefix which is also suffix，也就是“最长的、既是前缀又是后缀的真前缀长度”。

例如模式串：

a b a b a

它的某些位置前缀表会记录：当前已经匹配到这里时，如果下一位失败，模式串可以退回到哪个长度继续比较。

这听起来抽象，但核心目的很简单：失败后不要把模式串指针退回到 0，而是退回到一个更合理的位置。

构建 lps 数组

下面是构建 lps 数组的基本实现。

vector<int> buildLps(string pattern) {
    vector<int> lps(pattern.size(), 0);
    int length = 0;
    int i = 1;

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

    return lps;
}

int[] buildLps(String pattern) {
    int[] lps = new int[pattern.length()];
    int length = 0;
    int i = 1;

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

    return lps;
}

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1

    return lps

int[] BuildLps(string pattern)
{
    int[] lps = new int[pattern.Length];
    int length = 0;
    int i = 1;

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

    return lps;
}

这段代码的核心变量是 length。它表示当前已经找到的最长相同前后缀长度。当字符匹配时，这个长度可以增加；当不匹配时，就根据之前的 lps 信息回退。

使用 KMP 查找模式串

有了 lps 数组，就可以进行 KMP 匹配。

int kmpSearch(string text, string pattern) {
    if (pattern.empty()) {
        return 0;
    }

    vector<int> lps = buildLps(pattern);
    int i = 0;
    int j = 0;

    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;

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

    return -1;
}

int kmpSearch(String text, String pattern) {
    if (pattern.length() == 0) {
        return 0;
    }

    int[] lps = buildLps(pattern);
    int i = 0;
    int j = 0;

    while (i < text.length()) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;

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

    return -1;
}

def kmp_search(text, pattern):
    if len(pattern) == 0:
        return 0

    lps = build_lps(pattern)
    i = 0
    j = 0

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1

            if j == len(pattern):
                return i - j
        elif j > 0:
            j = lps[j - 1]
        else:
            i += 1

    return -1

int KmpSearch(string text, string pattern)
{
    if (pattern.Length == 0)
    {
        return 0;
    }

    int[] lps = BuildLps(pattern);
    int i = 0;
    int j = 0;

    while (i < text.Length)
    {
        if (text[i] == pattern[j])
        {
            i++;
            j++;

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

    return -1;
}

KMP 匹配时，主串指针 i 不会因为模式串失败而回退。失败时，如果模式串已经匹配了一部分，就通过 lps 调整模式串指针 j。

KMP 的复杂度

KMP 由两部分组成：

构建 lps 数组，时间复杂度是 $O(m)$ 。
扫描主串完成匹配，时间复杂度是 $O(n)$ 。

因此总时间复杂度是 $O(n + m)$ ，其中 $n$ 是主串长度， $m$ 是模式串长度。

额外空间主要来自 lps 数组，因此空间复杂度是 $O(m)$ 。

KMP 应该怎么学

KMP 对初学者来说比较抽象，不建议一开始就死记代码。

更好的学习顺序是：

先理解暴力匹配为什么会重复比较。
再理解模式串内部的相同前后缀可以提供回退依据。
然后理解 lps 数组保存的不是字符，而是可复用的匹配长度。
最后再看完整代码如何根据 lps 调整模式串指针。

只要你能理解“失败时主串不回退，模式串根据前缀表回退”，就已经抓住了 KMP 最重要的思想。

本节小结

KMP 算法通过前缀表记录模式串内部的重复结构，从而在匹配失败时避免主串指针回退。

暴力匹配最坏可能是 $O(nm)$ ，而 KMP 可以做到 $O(n + m)$ 。KMP 的难点在于前缀表，但它的核心目标很清楚：利用已经匹配过的信息，减少重复比较。