字符串匹配问题

MrHe··4 min read

这问题太经典了，基本上是面试必考，笔试常见。问题很简单：给你一个字符串 s（通常叫主串），再给你一个字符串 p（叫模式串），让你在 s 里面找到 p 第一次出现的位置，找不到就返回 -1。

比如 s = "ababcabcacbab"，p = "abcac"，p 在 s 的第 5 个位置（下标为 4）出现了，咱么就返回 4。如果 p = "abx"，在 s 里找不到，就返回 -1。

拿到这种题，别慌，先上最朴素、最符合直觉的解法。

解法一：暴力中的暴力，简单又粗暴

啥是暴力解法？就是完全不动脑子，模拟人眼查找的过程。

我是怎么用眼睛找的？

  1. 把 p 对齐 s 的第 0 个位置，一个一个字符比。s[0] 对 p[0]，s[1] 对 p[1]... 诶，s[2] 是 a，p[2] 是 c，不匹配。失败。

  2. 行，那把 p 往后挪一位，对齐 s 的第 1 个位置，再一个一个字符比。s[1] 对 p[0]，s[2] 对 p[1]... 又失败了。

  3. 不断重复这个过程，把 p 从 s 的第 0 位开始，挪到第 1 位，第 2 位... 直到 s 剩下的长度都不够 p 长了，就没必要再比了。

这个过程，是不是很简单？翻译成代码就行了。

public class StringMatching {

    // 解法一：暴力匹配
    public static int bruteForce(String s, String p) {
        if (s == null || p == null || s.length() < p.length()) {
            return -1;
        }
        if (p.isEmpty()) {
            return 0;
        }

        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();

        int n = sChars.length;
        int m = pChars.length;

        // i 是 s串的起始匹配点
        for (int i = 0; i <= n - m; i++) {
            // j 是 p串的指针
            int j = 0;
            while (j < m && sChars[i + j] == pChars[j]) {
                j++;
            }
            // 如果 j 走完了整个 p串，说明匹配成功
            if (j == m) {
                return i;
            }
        }

        // 遍历完所有可能的起始点，都没成功
        return -1;
    }
}

这代码逻辑清晰，两层循环。外层循环变量 i 控制 s 的起始匹配位置，内层 while 循环（或用 for 也一样）逐个字符比较。

复杂度分析： 假设 s 的长度是 N，p 的长度是 M。 外层循环最多走 N - M + 1 次，近似看作 N 次。 内层循环最多走 M 次。 所以，时间复杂度是 O(N * M)。

这解法在数据量小的时候完全没问题，简单粗暴有效。但如果 N 和 M 都很大，比如都是 10^5 级别，N * M 就是 10^10，那肯定超时了。

问题出在哪？每次匹配失败，s 的指针 i 都只是简单地 i++，然后 p 的指针 j 又回到了 0。这里面有大量的重复比较，信息完全被浪费了。比如 s="aaaa...aaab"，p="aaab"，每次匹配到最后一位才失败，前面的比较都白做了。

怎么优化？这就是经典算法 KMP 要干的事了。

解法二：KMP 算法，一次漂亮的降维打击

KMP 算法的核心思想，就是利用匹配失败后的信息，让模式串 p 尽可能地向右多移动几位，而不是傻傻地只移动一位。

咱么再回到暴力解法的失败现场： 当 s[i+j] 和 p[j] 匹配失败时，我们已经知道了 s 的子串 s[i...i+j-1] 和 p 的前缀 p[0...j-1] 是完全匹配的。

KMP 的灵魂拷问来了：我们能不能不回退 s 的指针 i，只移动 p 的指针 j？

答案是可以的。当 p[j] 匹配失败时，我们希望把 p 整个串向右滑动，滑到一个新的位置，使得 p 的某个前缀，能和刚刚在 s 中匹配上的那部分 s[i...i+j-1] 的某个后缀对齐。

因为 s[i...i+j-1] 和 p[0...j-1] 是相等的，所以这个问题就转化成了：在 p[0...j-1] 这个子串中，找一个最长的前缀，使得它等于该子串的某个后缀。

听起来有点绕，上图！ 假设 p = "ababc"，在某个位置匹配到 j=4 时失败了。 此时已经匹配上的部分是 p[0...3]，也就是 "abab"。

s:  ... a b a b c ...
p:      a b a b c
               ^--- 假设在这里，s 串对应的字符不是 c，失败了

此时 p[0...3] 是 "abab"。我们要找这个字符串的 "最长公共前后缀"。

  • 前缀有: "a", "ab", "aba"

  • 后缀有: "b", "ab", "bab" 最长的公共部分是 "ab"，长度为 2。

这个 "2" 意味着什么？意味着我们可以把 p 向右滑动，让 p 的前缀 "ab" (长度为2) 对齐刚刚匹配上的那段 s 串的后缀 "ab"。

原匹配:
s:  ... a b a b c ...
p:      a b a b c
           ^--- j = 4

滑动后:
s:  ... a b a b c ...
p:          a b a b c
           ^--- 新的 j = 2

看，s 的指针根本没动！我们只是把 p 的指针 j 从 4 拨回到了 2，然后继续用 s 当前的字符去和 p[2] 比较。这就避免了 s 指针的回溯，让整个匹配过程变成了 O(N) 级别。

这个 "最长公共前后缀" 的长度，我们可以预处理出来，存到一个数组里，通常叫做 next 数组。next[j] 就表示 p[0...j-1] 这个子串的最长公共前后缀的长度。

第一步：构建 next 数组

这个过程是 p 串自己和自己匹配的过程。 next[0] 规定是 0。 next[i] 的值依赖于 next[i-1]。

  • cn 代表当前最长公共前后缀的长度，也代表下一个要比较的字符位置。

  • 我们想求 next[i]，就要比较 p[i-1] 和 p[cn]。

  • 如果相等，next[i] = cn + 1。

  • 如果不相等，cn 就要往前跳，cn = next[cn]，直到 cn 变成 0 或者找到一个匹配。

代码实现 next 数组：

// KMP 的核心：构建 next 数组
// next[i] 表示 p[0...i-1] 的最长相等前后缀的长度
private static int[] getNextArray(char[] p) {
    int m = p.length;
    if (m == 1) {
        return new int[]{0};
    }
    int[] next = new int[m];
    next[0] = 0;
    int cn = 0; // 当前最长公共前后缀的长度，也是下一个要比较字符的索引
    int i = 1;
    while (i < m) {
        if (p[i] == p[cn]) {
            next[i++] = ++cn;
        } else if (cn > 0) {
            // 不匹配，cn 向前回溯
            cn = next[cn - 1];
        } else {
            // cn 已经回溯到0了，还是不匹配
            next[i++] = 0;
        }
    }
    return next;
}

注：next 数组的定义有很多种，比如整体右移一位，首位置为-1，我这里用的是长度定义，个人觉得更直观。

第二步：KMP 匹配过程 有了 next 数组，匹配过程就顺了。

// 解法二：KMP 算法
public static int kmp(String s, String p) {
    if (s == null || p == null || s.length() < p.length()) {
        return -1;
    }
    if (p.isEmpty()) {
        return 0;
    }

    char[] sChars = s.toCharArray();
    char[] pChars = p.toCharArray();
    int n = sChars.length;
    int m = pChars.length;

    int[] next = getNextArray(pChars);

    int i = 0; // s串的指针
    int j = 0; // p串的指针
    while (i < n) {
        if (sChars[i] == pChars[j]) {
            i++;
            j++;
        } else if (j > 0) {
            // 匹配失败，j 根据 next 数组回溯，i 不动
            j = next[j - 1];
        } else {
            // j 已经是 0 了，还是不匹配，说明 s[i] 这个字符不行
            i++;
        }

        // 如果 j 走完了整个 p串，说明匹配成功
        if (j == m) {
            return i - j; // 返回匹配的起始位置
        }
    }
    return -1;
}

复杂度分析：

  • getNextArray 的时间复杂度是 O(M)。虽然里面有 while 循环和回溯，但 cn 指针总共增加的次数不会超过 M，所以总操作是 O(M) 的。

  • kmp 匹配过程的时间复杂度是 O(N)。i 指针永不回头，只会前进。j 指针虽然会回溯，但 j 回溯的次数不会超过 i 前进的次数。所以总操作是 O(N) 的。

总的时间复杂度就是 O(N + M)，相比 O(N * M) 是质的飞跃。

解法三：大道至简，调就完事儿了

聊了这么多，在实际工作中，如果不是为了面试或者练习算法，谁会手写 KMP 啊？Java 语言本身就提供了非常强大的 API。

String 类自带的 indexOf 方法，就是干这个事的。

public class StringMatching {

    // 解法三：调用库函数
    public static int useIndexOf(String s, String p) {
          // 防御性编程还是得有
        if (s == null || p == null) {
            return -1;
        }
        return s.indexOf(p);
    }
}

一行代码搞定，舒服。

你可能会问，indexOf 底层用的是什么算法？是暴力吗？

当然不是。indexOf 的底层实现经过了高度优化。在早期的 JDK 版本中，它可能就是暴力法。但在现代的 JDK（比如 OpenJDK 8 之后）中，它的实现会更加智能。对于较短的模式串，可能会使用一种优化的暴力匹配。对于较长的模式串，它会采用一种叫做 "Two-Way String Matching" 的算法变种（有点类似 Boyer-Moore 算法的思想，但更复杂），也可能是其他高效的算法。这些实现都是 native 方法，效率极高。

虽然我们不知道它具体用了哪种，但可以肯定的是，它的平均时间复杂度接近 O(N + M)，并且由于是 JVM 层面优化的，实际运行速度通常比我们自己手写的 KMP 还要快。

为啥还要学 KMP？

  1. 面试：面试官想看的不是你会不会调 API，而是你解决问题的思维过程，从暴力到优化的能力。

  2. 思想：KMP 算法中利用 next 数组进行动态规划预处理，以及在匹配中“借用”历史信息的思想，在很多其他算法问题中都有应用。理解这种思想，比背下面试题重要得多。

总结一下

今天咱们从三个层面搞定了字符串匹配问题：

  1. 暴力解法：O(N * M)，最直观，是思考的起点。编码简单，但效率最低。

  2. KMP 算法：O(N + M)，面试核心。关键在于理解 next 数组如何帮助模式串在匹配失败时进行“智能”跳转，从而避免主串指针的回溯。这是从暴力到优化的思维飞跃。

  3. 库函数 indexOf：实际工作中的首选。效率高、稳定、代码简洁。但作为算法学习者，要做到知其然，也要知其所以然。

  • #5a2x56ym5liy5yy56ywn