字符串匹配是计算机最基础的操作之一——搜索关键词、文本替换、DNA 序列比对。这篇从暴力匹配讲到 KMP，再到 BM 和 Sunday 算法。

一、暴力匹配

public class BruteForce {

    public static int indexOf(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;  // 匹配成功
            }
        }
        return -1;
    }
}

时间复杂度： O(n × m)
空间复杂度： O(1)

最坏情况举例：

主串：   "AAAAAA...AAAAAB"
模式串： "AAAAB"
每一趟都要比到最后才发现不匹配 → 极低效

二、KMP 算法

1. 核心思想

KMP 的核心思想是：匹配失败时，主串指针不回溯，利用已匹配部分的信息，将模式串向右滑动尽可能远的距离。

主串：   "ABABABC"
模式串： "ABABC"

匹配到第 5 个字符时失败：
  A B A B A B C
  A B A B C
  ↑       ↑
  i=4    j=4 不匹配

暴力做法：i 回退到 1，j 回退到 0
KMP 做法：i 不动，j 跳到 2
  因为已匹配的 "ABAB" 中，前缀 "AB" = 后缀 "AB"

2. next 数组

next[j] 表示当模式串第 j 个字符匹配失败时，j 应该回退到的位置。

next[0] = -1（第一个字符就失败的情况）
next[1] = 0（第二个字符失败，回到开头）

计算规则：
  next[j] = 模式串 [0:j-1] 中最长相等前后缀的长度

3. 手算 next 数组

模式串： "abaabcac"

j=0：next[0] = -1

j=1：T[0:0]="" → 无子串 → next[1] = 0

j=2：T[0:1]="ab" → 前缀{"a"} 后缀{"b"} → 无相等 → next[2] = 0

j=3：T[0:2]="aba" → 前缀{"a","ab"} 后缀{"a","ba"} → 相等"a"长度1 → next[3]=1

j=4：T[0:3]="abaa" → 前缀{"a","ab","aba"} 后缀{"a","aa","baa"} → 相等"a"长度1 → next[4]=1

j=5：T[0:4]="abaab" → 前缀{"a","ab","aba","abaa"} 后缀{"b","ab","aab","baab"} → 相等"ab"长度2 → next[5]=2

j=6：T[0:5]="abaabc" → 前缀和后缀 → 无相等 → next[6]=0 → 优化后=2

j=7：T[0:6]="abaabca" → 相等"a"长度1 → next[7]=1

next = [-1, 0, 0, 1, 1, 2, 0, 1]

4. KMP 匹配代码

public class KMP {

    public static int[] getNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;
        int i = 0, j = -1;

        while (i < m - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public static int indexOf(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return 0;

        int[] next = getNext(pattern);
        int i = 0, j = 0;

        while (i < n && j < m) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        return j == m ? i - j : -1;
    }
}

5. next 数组的优化——nextval

/**
 * 当 pattern[i] == pattern[j] 时，
 * 即使跳转到 j 也会匹配失败，所以继续跳转
 */
public static int[] getNextVal(String pattern) {
    int m = pattern.length();
    int[] nextval = new int[m];
    nextval[0] = -1;
    int i = 0, j = -1;

    while (i < m - 1) {
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
            if (pattern.charAt(i) != pattern.charAt(j)) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
    return nextval;
}

三、BM 算法

BM 算法从模式串的尾部开始匹配，利用坏字符规则和好后缀规则。

1. 坏字符规则

模式串从右向左比较
遇到不匹配的字符（坏字符），移动模式串使坏字符对齐

例子：
  主串：   "EXAMPLE"
  模式串："APPLES"
           ↑
  坏字符：'E' 在模式串中不存在
  模式串整体移到 'E' 后面

2. 好后缀规则

已匹配的部分称为"好后缀"
查找好后缀在模式串中是否在其他位置出现
如果出现，移动到该位置；否则移动到好后缀的前缀位置

四、Sunday 算法

Sunday 算法是比 BM 更快的一种匹配算法，理解起来也更简单。

1. 核心思想

匹配失败时，关注主串中模式串后面一个位置的字符
根据该字符在模式串中的位置决定移动距离

例子：
  主串：   "substring searching"
  模式串："search"

第一趟匹配：
  substring searching
  search
  ↑i=0, j=0 匹配
  ...
  ↑i=3, j=3 不匹配（'b' ≠ 'a'）
  模式串后面的字符是 't'
  't' 在模式串中不存在 → 直接移动 7 位

2. Sunday 算法实现

public class Sunday {

    public static int indexOf(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return 0;

        // 构建偏移表
        int[] shift = new int[256];
        for (int i = 0; i < 256; i++) {
            shift[i] = m + 1;  // 默认偏移 = 模式串长度 + 1
        }
        for (int i = 0; i < m; i++) {
            shift[pattern.charAt(i)] = m - i;
        }

        int i = 0;  // 主串指针
        while (i <= n - m) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) return i;  // 匹配成功

            // 移动：看主串中模式串后的第一个字符
            if (i + m < n) {
                i += shift[text.charAt(i + m)];
            } else {
                break;
            }
        }
        return -1;
    }
}

3. Sunday vs KMP vs BM

算法	平均时间	最坏时间	预处理	实现难度
暴力	O(nm)	O(nm)	无	⭐
KMP	O(n+m)	O(n+m)	next数组	⭐⭐⭐
BM	O(n/m)	O(nm)	坏字符+好后缀	⭐⭐⭐⭐
Sunday	O(n/m)	O(nm)	偏移表	⭐⭐

实际使用建议：
  一般场景 → KMP（稳定，考研必考）
  文本搜索 → Sunday（代码简单，平均快）
  性能极致 → BM（最复杂，也最快）

五、408 考研常见考题

题1：手算 next 数组

模式串 "ababa" 的 next 数组

j=0: next[0] = -1
j=1: next[1] = 0  
j=2: "ab" → 无相等 → next[2]=0
j=3: "aba" → "a"长度1 → next[3]=1
j=4: "abab" → "ab"长度2 → next[4]=2

next = [-1, 0, 0, 1, 2]

题2：KMP 匹配过程

主串 "ababcabcacbab"，模式串 "abcac"
请用 KMP 算法写出匹配过程

next = [-1, 0, 0, 0, 1]

第一趟：ababcabcacbab
        abcac
        i=3失败,j=3 → next[3]=0
    
第二趟：ababcabcacbab
           abcac
           i=3失败,j=0 → next[0]=-1 → i=4,j=0

第三趟：ababcabcacbab
            abcac
            i=4失败,j=0 → next[0]=-1 → i=5,j=0

第四趟：ababcabcacbab
             abcac
             匹配成功！i=9,j=5 → 位置=9-5=4

题3：模式串的优化

模式串 "aaaaaaab"
next 数组：[-1, 0, 1, 2, 3, 4, 5, 6]
nextval 数组：[-1, -1, -1, -1, -1, -1, -1, 6]

优化效果：
  当遇到 'b' 之前所有字符都是 'a'
  在 'a' 上匹配失败时，跳到任何一个 'a' 结果都一样
  nextval 直接跳到第一个字符，减少不必要的比较

六、字符串匹配在实际开发中的应用

// 1. Java String.indexOf() 使用的就是暴力匹配的优化版
String text = "Hello World";
int index = text.indexOf("World");

// 2. 文本编辑器的查找功能
//    通常使用 Sunday 或 BM 算法

// 3. 入侵检测系统
//    使用 AC 自动机（Aho-Corasick）多模式匹配

// 4. DNA 序列比对
//    使用 BLAST 等专门算法

总结

暴力匹配 → O(nm) → 简单但慢
KMP      → O(n+m) → 考研重点，能手算 next 数组
Sunday   → O(n/m) → 代码简单，实际应用中常用
BM       → O(n/m) → 最复杂，最快

考研重点：手算 next 数组、nextval 优化、KMP 匹配过程

---

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫 实战干货，不让你白来。