字符串匹配算法¶

一、暴力匹配（BF, Brute Force）¶

主串 n，模式串 m，逐个位置比对。

时间：O(n*m)
简单，但慢。

二、KMP¶

利用已匹配部分的信息，主串指针不回退。

next 数组¶

next[i] 表示模式串前 i 个字符组成的子串，最长相等真前缀和真后缀的长度。

匹配失败时，模式串跳到 next[k] 位置，主串指针不动。

时间¶

O(n + m)。

代码¶

int[] buildNext(String p) {
    int[] next = new int[p.length()];
    int j = 0;
    for (int i = 1; i < p.length(); i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) {
            j = next[j - 1];
        }
        if (p.charAt(i) == p.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}

三、Boyer-Moore（BM）¶

从右往左匹配，利用坏字符和好后缀规则，跳过更多字符。

实践中比 KMP 快，grep 用的就是 BM。
复杂，面试一般讲思想。

四、Sunday¶

从左往右，看主串当前参与匹配的最右字符在模式串中是否出现：

出现：对齐到该位置。
不出现：跳过整个模式串。

比 BM 简单，跳得远。

五、对比¶

算法	时间	特点
BF	O(n*m)	简单
KMP	O(n+m)	主串不回退
BM	平均 O(n/m)	最快，复杂
Sunday	平均快	简单

六、实际应用¶

Java String.indexOf 用的是改良的暴力匹配。
专业搜索用 KMP / BM。
正则引擎基于 NFA，本质是状态机。

高频追问

KMP 的 next 数组为什么要这样求？本质是模式串的自我匹配。
BM 为什么快？利用了已匹配字符的信息，一次跳多位。