字符串

字符串匹配算法

暴力匹配 Brute-Force

短串匹配长串，从短串第一个匹配长串第一个

如果短串匹配了长串，则短串第二个匹配长串第二个
如果短串第二个不匹配长串第二个，则短串开始位置移到长串第二个位置
短串第一个跟长串第二个进行匹配，直到短串的尾部位置等于长串尾部位置

字符串搜索算法 BM Boyer-Moore

Boyer-Moore（BM）算法是一种高效的字符串搜索算法，由 Robert S. Boyer 和 J Strother Moore 于 1977 年提出。其核心优势是在匹配失败时能一次性跳过多个字符，而非逐个移动，因此在实际应用中（如文本编辑器的查找功能）效率远高于朴素算法（Naive Algorithm），甚至优于 KMP 算法。

BM 算法的核心思想

与传统的 “从左到右匹配” 不同，BM 算法采用 “从右到左匹配”，并结合两个启发式规则（坏字符规则、好后缀规则）来决定匹配失败时模式串（pattern）向右移动的距离，从而减少不必要的比较。

模式串：待搜索的子串（如 abc）。
文本串：被搜索的主串（如 aababc）。

关键规则：坏字符与好后缀

1. 坏字符规则（Bad Character Rule）

定义：在从右到左的匹配过程中，文本串中第一个与模式串不匹配的字符称为 “坏字符”。
移动距离：
- 若坏字符在模式串中存在，则模式串向右移动，使模式串中最靠右的该字符与文本串的坏字符对齐。
- 若坏字符在模式串中不存在，则模式串直接移动到坏字符右侧（移动距离 = 模式串长度）。
示例：
文本串：HERE IS A SIMPLE EXAMPLE
模式串：EXAMPLE
首次匹配时，坏字符为文本串的 S（模式串对应位置是 E），S 不在模式串中，因此模式串直接右移 7 位（长度）。

2. 好后缀规则（Good Suffix Rule）

定义：在从右到左的匹配过程中，模式串与文本串已匹配的后缀部分称为 “好后缀”。
移动距离：
- 若模式串中存在与好后缀完全相同的前缀子串，则模式串向右移动，使该前缀与好后缀对齐。
- 若不存在，则寻找好后缀的最长前缀（该前缀同时也是模式串的前缀），移动对应距离。
- 若好后缀为空（无匹配部分），则移动 1 位。
示例：
文本串：ABCABCDABABCDABCDABDE
模式串：ABCDABD
匹配时好后缀为 D（模式串末尾 D 与文本串匹配），模式串中左侧也有 D，因此右移使左侧 D 与文本串 D 对齐。

3. 最终移动距离

BM 算法取坏字符规则与好后缀规则计算出的最大移动距离作为实际移动步数，以最大化跳过的字符数。

预处理：加速规则计算

为快速应用上述规则，需对模式串进行预处理，生成两个辅助数组：

1. 坏字符表（bc）

记录模式串中每个字符最后出现的索引（位置）。
格式：bc[字符] = 索引（若字符不存在，值为 -1）。
示例：模式串 ABCABD
字符 A B C D 其他
索引 3 4 2 5 -1

字符	A	B	C	D	其他
索引	3	4	2	5	-1

2. 好后缀表（gs）

记录模式串中每个位置的好后缀对应的最大移动距离。
格式：gs[i] = 移动距离（i 是模式串中好后缀的起始索引）。
计算逻辑：
1. 找到好后缀的最长前缀子串（与模式串前缀匹配）。
2. 移动距离 = 模式串长度 - 该前缀的结束索引 - 1。

Java 实现代码

public class BoyerMoore {

    private static final int ASCII_SIZE = 256; // 假设字符为ASCII码

    /**
     * BM算法搜索模式串在文本串中的位置
     * @param text 文本串
     * @param pattern 模式串
     * @return 首次出现的索引，未找到返回-1
     */
    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0 || n < m) return -1;

        // 预处理：构建坏字符表
        int[] bc = buildBadCharTable(pattern);
        // 预处理：构建好后缀表
        int[] gs = buildGoodSuffixTable(pattern);

        int i = 0; // 文本串当前匹配的起始索引
        while (i <= n - m) {
            int j;
            // 从右到左匹配模式串
            for (j = m - 1; j >= 0; j--) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // 找到坏字符，退出循环
                }
            }
            if (j < 0) {
                return i; // 匹配成功，返回起始索引
            }

            // 计算坏字符规则的移动距离
            char badChar = text.charAt(i + j);
            int bcMove = j - bc[badChar];
            // 计算好后缀规则的移动距离
            int gsMove = 1;
            if (j < m - 1) { // 存在好后缀
                gsMove = gs[j + 1];
            }

            // 取最大移动距离，确保不后退
            i += Math.max(bcMove, gsMove);
        }
        return -1; // 未找到
    }

    /**
     * 构建坏字符表：记录每个字符在模式串中最后出现的索引
     */
    private static int[] buildBadCharTable(String pattern) {
        int[] bc = new int[ASCII_SIZE];
        // 初始化所有字符为-1（表示不存在）
        for (int i = 0; i < ASCII_SIZE; i++) {
            bc[i] = -1;
        }
        // 记录每个字符最后出现的位置
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            bc[c] = i;
        }
        return bc;
    }

    /**
     * 构建好后缀表：记录每个位置的好后缀对应的移动距离
     */
    private static int[] buildGoodSuffixTable(String pattern) {
        int m = pattern.length();
        int[] gs = new int[m];
        int[] suffix = new int[m]; // 辅助数组：suffix[k]表示长度为k的好后缀在模式串中最右的起始索引

        // 初始化suffix数组
        suffix[0] = -1; // 长度为0的后缀无意义
        for (int i = 0; i < m - 1; i++) {
            int k = 0; // 好后缀长度
            int j = i;
            // 从i向左，与模式串末尾向右的k位比较
            while (j >= 0 && pattern.charAt(j) == pattern.charAt(m - 1 - k)) {
                j--;
                k++;
                suffix[k] = j + 1; // 记录起始索引（j+1是因为j已减1）
            }
        }

        // 计算gs数组
        for (int i = 0; i < m; i++) {
            gs[i] = m; // 默认移动m位
        }
        int j = 0;
        for (int i = m - 1; i >= 0; i--) {
            // 若存在长度为i+1的前缀与好后缀匹配
            if (suffix[i + 1] == 0) {
                for (; j < m - 1 - i; j++) {
                    if (gs[j] == m) {
                        gs[j] = m - 1 - i;
                    }
                }
            }
        }
        // 若存在好后缀的匹配子串，更新移动距离
        for (int i = 0; i < m - 1; i++) {
            gs[m - 1 - suffix[i + 1]] = m - 1 - i;
        }
        return gs;
    }

    public static void main(String[] args) {
        String text = "HERE IS A SIMPLE EXAMPLE";
        String pattern = "EXAMPLE";
        int index = search(text, pattern);
        System.out.println("模式串首次出现的位置：" + index); // 输出：15
    }
}

BM 算法的优势与适用场景

优势：
- 平均时间复杂度为 O(n/m)（n 为文本串长度，m 为模式串长度），最坏情况为 O (n*m)，但实际表现优异。
- 对长文本和模式串的搜索效率极高，尤其在文本中存在大量不匹配字符时（如英文文本）。
适用场景：
- 文本编辑器的 “查找” 功能（如 VS Code、Word 的搜索）。
- 基因序列匹配、日志分析等大规模文本处理场景。

总结

BM 算法的核心是 “从右到左匹配 + 最大化移动距离”，通过坏字符和好后缀规则减少无效比较，是工程中最常用的字符串搜索算法之一。理解其预处理逻辑（坏字符表、好后缀表）是掌握该算法的关键。

KMP

漫画：什么是KMP算法？ | 黄杰夫教程

字符串 a b a b c

prefix table 做短串前缀表(next数组)

a b a b c

前缀表：

a
a b
a b a
a b a b
a b a b c

把每个前缀当成一个独立的字符串，对于每一个字符串找出最长公共前后缀，最长公共前后缀要比原始字符串要短，所以最后一组不需要 a 的最长公共前后缀是0 ab 的最长公共前后缀是0 aba 的最长公共前后缀是1 如果前缀是ab 后缀是ba就不相同了，所以只能是前缀是a，后缀也是a所以长度是1 abab 的最长公共前后缀是2 前缀ab 后缀ab 长度是2 最后一组抛弃，最开始用-1表示所以最后的前缀表是

-1,0,0,1,2

前缀表对应的下标是

0,1,2,3,4

对应关系：

 0,1,2,3,4 下标
 a,b,a,b,c 字符串
-1,0,0,1,2 最长公共前后缀长度

比如下标3的位置没有匹配上，则取出3下面的最长公共前后缀长度是1，然后把下标是1的位置拉倒当前3下标的位置。

KMP 算法（Knuth-Morris-Pratt 算法）是一种高效的字符串匹配算法，由 Knuth、Morris、Pratt 三人共同提出。它通过预处理模式串（待匹配的子串），构建「部分匹配表（Partial Match Table）」，在匹配失败时避免回溯文本串指针，从而将时间复杂度优化至 O(n + m)（n 为文本串长度，m 为模式串长度），远优于朴素算法的 O (n*m)。

KMP 算法的核心思想

传统的朴素匹配算法在匹配失败时，文本串和模式串的指针都会回溯（例如文本串指针 i 回退到 i-j+1，模式串指针 j 回退到 0），导致大量重复比较。

KMP 算法的优化点在于：匹配失败时，文本串指针 i 不回溯，仅通过模式串的预处理信息，让模式串指针 j 回退到合适的位置，从而减少无效比较。

关键概念：部分匹配表（Partial Match Table，PMT）

部分匹配表（也称「前缀函数」）是 KMP 的核心，它用于记录模式串中「最长前缀后缀匹配长度」。

1. 前缀与后缀

前缀：模式串中除最后一个字符外，所有以第一个字符开头的连续子串。
例：模式串 ABABC 的前缀为 A 、AB 、ABA 、ABAB 。
后缀：模式串中除第一个字符外，所有以最后一个字符结尾的连续子串。
例：模式串 ABABC 的后缀为 C 、BC 、ABC 、BABC 。

2. 最长前缀后缀匹配长度

对于模式串的每个位置 j（从 0 开始），PMT[j] 表示「模式串中 0~j 子串的最长前缀与后缀（非整个子串）的匹配长度」。

示例：模式串 ABABC 的 PMT 表

模式串索引 `j`	0	1	2	3	4
子串 `0~j`	A	AB	ABA	ABAB	ABABC
`PMT[j]`	0	0	1	2	0

j=0（子串 A）：无前缀 / 后缀，PMT[0]=0。
j=2（子串 ABA）：最长匹配前缀 A 与后缀 A，长度 1 → PMT[2]=1。
j=3（子串 ABAB）：最长匹配前缀 AB 与后缀 AB，长度 2 → PMT[3]=2。

3. PMT 的作用

当文本串 text[i] 与模式串 pattern[j] 匹配失败时，模式串指针 j 无需回退到 0，而是回退到 PMT[j-1]（即 j = PMT[j-1]），此时文本串指针 i 继续向后移动。

这是因为 PMT[j-1] 表示「0~j-1 子串中已匹配的最长前缀后缀长度」，利用这段重叠部分可直接继续匹配，避免重复比较。

KMP 算法步骤

预处理模式串：计算部分匹配表（PMT）。
匹配阶段：用 PMT 指导模式串指针回退，高效匹配文本串与模式串。

Java 实现代码

1. 计算部分匹配表（PMT）

/**
 * 计算模式串的部分匹配表（PMT）
 * @param pattern 模式串
 * @return PMT数组，长度与模式串相同
 */
private static int[] computePMT(String pattern) {
    int m = pattern.length();
    int[] pmt = new int[m];
    int len = 0; // len表示当前最长前缀后缀匹配长度（初始为0）

    // 从索引1开始计算（索引0的PMT必为0）
    for (int i = 1; i < m; ) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            // 若当前字符匹配，长度+1，i后移
            len++;
            pmt[i] = len;
            i++;
        } else {
            if (len != 0) {
                // 不匹配且len>0，回退到上一个可能的匹配长度
                len = pmt[len - 1];
            } else {
                // len=0仍不匹配，PMT[i]为0，i后移
                pmt[i] = 0;
                i++;
            }
        }
    }
    return pmt;
}

2. KMP 匹配算法

/**
 * KMP算法匹配文本串与模式串
 * @param text 文本串
 * @param pattern 模式串
 * @return 模式串在文本串中首次出现的索引，未找到返回-1
 */
public static int kmpSearch(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    if (m == 0 || n < m) {
        return -1;
    }

    // 1. 预处理：计算PMT
    int[] pmt = computePMT(pattern);

    // 2. 匹配阶段
    int i = 0; // 文本串指针
    int j = 0; // 模式串指针
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            // 字符匹配，双指针后移
            i++;
            j++;
            // 模式串完全匹配，返回起始索引
            if (j == m) {
                return i - j;
            }
        } else {
            if (j != 0) {
                // 匹配失败，模式串指针回退到PMT[j-1]
                j = pmt[j - 1];
            } else {
                // j=0仍不匹配，文本串指针后移
                i++;
            }
        }
    }
    // 未找到匹配
    return -1;
}

3. 测试示例

public static void main(String[] args) {
    String text = "ABABABCABABABCABABABC";
    String pattern = "ABABC";
    int index = kmpSearch(text, pattern);
    System.out.println("模式串首次出现的位置：" + index); // 输出：2
}

KMP 算法的优势与适用场景

优势：
- 时间复杂度稳定在 O (n + m)，无最坏情况退化（对比 BM 算法的最坏 O (n*m)）。
- 无需回溯文本串，适合处理流式数据（如网络传输中的字符串匹配）。
适用场景：
- 文本编辑器的查找替换、DNA 序列匹配、日志关键字检索等。
- 对匹配效率要求高，且模式串与文本串较长的场景。

总结

KMP 算法的核心是部分匹配表（PMT），其本质是利用模式串自身的前缀后缀重叠信息，避免匹配失败时的无效回溯。掌握 PMT 的计算逻辑（尤其是指针回退规则），就能理解 KMP 高效的原因。相比朴素算法，KMP 在长文本匹配中优势明显，是字符串处理的基础算法之一。

Trie

Trie（发音为 “try”），又称前缀树或字典树，是一种专门用于处理字符串匹配的数据结构，尤其适合前缀匹配和字符串检索场景。它通过共享字符串的公共前缀来节省存储空间，同时能高效地完成字符串的插入、查询和删除操作。

Trie 的核心结构

Trie 是一种多叉树，每个节点代表一个字符，从根节点到某一叶子节点的路径拼接起来，形成一个完整的字符串。

关键特性：

根节点为空：不存储任何字符，是所有字符串的起始点。
节点包含子节点：每个节点有多个子节点（通常用数组或哈希表存储），每个子节点对应一个字符。
标记结束：节点中包含一个标志（如 isEnd），表示从根节点到当前节点的路径是否构成一个完整的字符串。

示例：存储字符串 `["apple", "app", "banana", "band"]` 的 Trie 结构

        根节点
       /    \
      a      b
     /      /
    p      a
   /      /
  p      n
 / \    / \
l   (end) d (end)
|
e (end)

路径 a→p→p 标记为 end，表示字符串 app。
路径 a→p→p→l→e 标记为 end，表示字符串 apple。

Trie 的核心操作（Java 实现）

1. 节点结构定义

class TrieNode {
    // 子节点：假设字符为小写字母，用数组存储（索引0-25对应'a'-'z'）
    TrieNode[] children;
    // 标记当前节点是否为字符串的结尾
    boolean isEnd;

    public TrieNode() {
        children = new TrieNode[26]; // 26个小写字母
        isEnd = false;
    }
}

2. Trie 类实现（插入、查询、前缀匹配）

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode(); // 根节点为空
    }

    /**
     * 插入字符串到Trie中
     */
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // 计算字符对应的索引（0-25）
            if (node.children[index] == null) {
                // 若子节点不存在，创建新节点
                node.children[index] = new TrieNode();
            }
            // 移动到子节点
            node = node.children[index];
        }
        // 标记字符串结束
        node.isEnd = true;
    }

    /**
     * 查询字符串是否在Trie中（完整匹配）
     */
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                // 子节点不存在，说明字符串不存在
                return false;
            }
            node = node.children[index];
        }
        // 必须是完整字符串（isEnd为true）
        return node.isEnd;
    }

    /**
     * 判断Trie中是否存在以prefix为前缀的字符串
     */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        // 只要前缀存在即可，无需是完整字符串
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // true（完整匹配）
        System.out.println(trie.search("app"));     // false（非完整字符串）
        System.out.println(trie.startsWith("app")); // true（存在前缀）
        trie.insert("app");
        System.out.println(trie.search("app"));     // true（插入后完整匹配）
    }
}

Trie 的时间与空间复杂度

时间复杂度：
插入、查询、前缀匹配的时间复杂度均为O(L)，其中 L 是字符串的长度（每个字符操作一次）。
空间复杂度：
取决于字符集大小（如 26 个字母）和存储的字符串总长度，最坏情况为O(N×L)（N 为字符串数量，L 为平均长度），但实际因共享前缀会节省空间。

Trie 的经典算法题

1. 实现 Trie（前缀树）（LeetCode 208）

题目：设计一个 Trie 类，支持 insert、search、startsWith 操作。

解法：如上述代码实现。

2. 单词搜索 II（LeetCode 212）

题目：给定一个字符矩阵和一个单词列表，找出矩阵中所有存在的单词。

思路：先用单词列表构建 Trie，再通过 DFS 遍历矩阵，结合 Trie 剪枝（若当前路径不在 Trie 中则停止搜索）。

public List<String> findWords(char[][] board, String[] words) {
    // 构建Trie
    Trie trie = new Trie();
    for (String word : words) {
        trie.insert(word);
    }

    Set<String> result = new HashSet<>();
    int m = board.length, n = board[0].length;
    boolean[][] visited = new boolean[m][n];

    // 遍历矩阵每个位置作为起点
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dfs(board, i, j, trie.root, "", result, visited);
        }
    }
    return new ArrayList<>(result);
}

private void dfs(char[][] board, int i, int j, TrieNode node, String current,
                 Set<String> result, boolean[][] visited) {
    // 边界判断
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]) {
        return;
    }

    char c = board[i][j];
    int index = c - 'a';
    // 若当前字符不在Trie中，剪枝
    if (node.children[index] == null) {
        return;
    }

    // 移动到子节点，更新当前字符串
    node = node.children[index];
    current += c;
    // 若当前路径是一个完整单词，加入结果
    if (node.isEnd) {
        result.add(current);
    }

    // 标记访问
    visited[i][j] = true;
    // 上下左右DFS
    dfs(board, i + 1, j, node, current, result, visited);
    dfs(board, i - 1, j, node, current, result, visited);
    dfs(board, i, j + 1, node, current, result, visited);
    dfs(board, i, j - 1, node, current, result, visited);
    // 回溯
    visited[i][j] = false;
}

3. 最长公共前缀（LeetCode 14）

题目：找出字符串数组中的最长公共前缀，若不存在则返回空字符串。

思路：用 Trie 存储所有字符串，从根节点开始，若当前节点只有一个子节点且不是字符串终点，则继续深入，直到不符合条件，路径即为最长公共前缀。

Trie 的适用场景

自动补全：如搜索引擎输入关键词时的联想提示（利用前缀匹配）。
拼写检查：判断单词是否存在于词典中（完整匹配）。
IP 路由查找：网络路由表中通过前缀匹配快速定位路由。
单词游戏：如 Scrabble 中判断单词是否有效。

总结

Trie 的核心优势在于前缀共享和高效的前缀匹配，尤其适合处理大量字符串且需要频繁前缀查询的场景。虽然其空间复杂度可能较高（取决于字符集），但时间效率远超哈希表（哈希表不支持前缀匹配，且存在哈希冲突）。在实际开发中，Trie 是处理字符串相关问题的重要工具。