---

上篇：第二十章、回溯算法
下篇：第二十二章、位运算技巧

第二十一章 字符串算法

在前面章节中，我们学习了回溯算法——一种通过 “枚举 + 剪枝” 来搜索所有可行解的策略。回溯的核心是决策树的遍历，适用于"排列、组合、子集、棋盘类"问题。

但有一类问题，它的输入不是数组或数字，而是字符串。字符串有其独特的结构——字符有序排列、可能包含重复、需要频繁进行"匹配"和"查找"操作。处理字符串的算法，与我们之前学过的通用算法有着截然不同的设计思路。

字符串算法：专门针对字符串的存储、匹配、查找、变换等问题而设计的算法家族，核心问题是在一个字符串中高效地查找另一个字符串的出现位置（即字符串匹配），以及围绕字符串的各种经典操作（回文判断、子串查找、数值转换等）。

字符串是面试中出现频率最高的题型之一——几乎每场技术面试都至少有一道字符串题。从最基础的"反转字符串"，到高阶的 KMP、Manacher 算法，字符串算法的跨度极大。本章将从字符串匹配的四大算法入手，再到四个经典实战，带你系统掌握字符串算法的核心技巧。

---

21.1 问题引入

举个简单的例子：在一段文本中查找某个关键词

假设有一篇长文本 text（长度 n）和一个关键词 pattern（长度 m），我们需要判断 pattern 是否出现在 text 中，如果出现，出现在哪些位置。

这是最经典的字符串匹配问题。直觉上，我们可以用"暴力法"逐位比较——但这样最坏需要比较 $O(n\times m)$ 次。当文本很长时（如搜索引擎索引数十亿网页），暴力法的效率远远不够。

【分析】如何高效地进行字符串匹配？

• 关键要素1：避免重复比较——暴力法中，匹配失败后主串指针回退，导致很多已经比较过的字符被重复比较
• 关键要素2：利用已知信息——匹配过程中已经获得的信息（如已匹配的前缀），能否帮助我们"跳过"不可能匹配的位置？
• 关键要素3：哈希加速——能否通过数值化的方式，快速判断两个子串是否相等？

不同的思路，诞生了不同的字符串匹配算法：

方法一：暴力匹配（Brute Force）

朴素的双重循环，主串和模式串逐位比较，失败则主串回退一位。

问题：主串指针的回退导致大量重复比较，最坏时间复杂度 $O(n\times m)$。

方法二：KMP 算法

利用模式串自身的结构信息（前缀函数 / next 数组），在匹配失败时主串指针不回退，仅移动模式串。

核心优势：KMP 消除了主串指针的回退，时间复杂度严格 $O(n+m)$。

方法三：Boyer-Moore 算法

从模式串的右端开始比较，利用"坏字符规则"和"好后缀规则"跳过不可能匹配的区域。

核心优势：在最佳情况下，BM 算法可以一次跳过 m 个字符，达到 $O(n/m)$ 的惊人效率。

方法四：Rabin-Karp 算法（滚动哈希）

将字符串映射为数值（哈希），通过"滚动"方式在 $O(1)$ 时间内计算新子串的哈希值，先比较哈希再比较字符串。

核心优势：对"多模式匹配"场景特别高效，哈希相同时才进行精确比较。

---

21.2 字符串匹配算法

21.2.1 暴力匹配（Brute Force）

暴力匹配是最直观的字符串匹配算法：用两个指针 i 和 j 分别指向主串和模式串的起始位置，逐个字符比较；若匹配失败，主串指针 i 回退到上次匹配起点的下一个位置，模式串指针 j 归零。

下面用 HTML 表格展示暴力匹配的逐步过程：

import java.util.ArrayList;
import java.util.List;

/**
 * 暴力匹配算法（Brute Force）
 * 时间复杂度：O(n × m) — 最坏情况下每个位置都要比较完整模式串
 * 空间复杂度：O(1)
 */
public class BruteForceSearch {

    /**
     * 在 text 中查找 pattern 的所有出现位置
     * @param text    主串
     * @param pattern 模式串
     * @return 所有匹配的起始索引列表
     */
    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (text == null || pattern == null || pattern.isEmpty()) {
            return result;
        }

        int n = text.length();
        int m = pattern.length();

        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            // 逐字符比较
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                result.add(i);  // 匹配成功
            }
        }
        return result;
    }
}

时间复杂度分析：

情况	时间复杂度	说明
最好情况	O(n)	第一个字符就不匹配，主串指针每次只前进一位
平均情况	O(n + m)	随机文本下，大部分位置在第一个字符就失配
最坏情况	O(n × m)	如 text=“AAAAAA”, pattern=“AAAB”，每个位置都几乎匹配完才失配

暴力法的问题：最坏情况下，主串指针 i 不断回退，导致大量重复比较。比如 text=“AAAAAAAB”, pattern=“AAAB”：前 3 个字符都匹配，第 4 个失配，然后 i 回退 1 位，又比较 3 个匹配……这种"匹配了很多又推倒重来"的行为，是暴力法效率低下的根源。

---

21.2.2 KMP 算法（next 数组详解）

KMP 算法（Knuth-Morris-Pratt）是字符串匹配领域最经典的算法之一。它的核心思想是：当匹配失败时，利用已经匹配过的信息，让主串指针不回退，只移动模式串。

KMP 的核心洞察：匹配失败时，已经比较过的模式串前缀中，可能存在"相同的前缀和后缀"——我们可以利用这个信息，将模式串滑动到合适的位置继续比较，而不用从头再来。

1. next 数组的定义与构造

next[j] 表示：当模式串的第 j 个字符匹配失败时，模式串应该滑动到哪个位置继续比较。

更严格的定义：

next[j] = 模式串 pattern[0...j-1] 中，最长相等真前后缀的长度。

其中 “真前后缀” 意味着前缀和后缀都不能是整个字符串本身。

next 数组约定：next[0] = -1（第一个字符失配时，模式串整体右移一位），next[1] = 0（只有单个字符，不存在真前后缀）。

2. next 数组的构造算法

next 数组可以通过模式串自身的"递推"来构造——利用已经求得的 next[0...j-1] 来计算 next[j]：

/**
 * 构造 next 数组
 * next[j] = pattern[0..j-1] 中最长相等真前后缀的长度
 * 约定 next[0] = -1
 */
private int[] buildNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = -1;

    int k = -1;  // k 表示当前最长相等前后缀的长度 - 1
    int j = 1;   // 从 j=1 开始计算

    while (j < m) {
        if (k == -1 || pattern.charAt(k) == pattern.charAt(j - 1)) {
            k++;
            next[j] = k;
            j++;
        } else {
            k = next[k];  // 回退：利用已求的 next 值
        }
    }
    return next;
}

构造 next 的本质：在模式串中用模式串自身做匹配！k 指针跟踪"已匹配的最长前缀末尾"，j 指针推进模式串的每个位置。当 pattern[k] != pattern[j-1] 时，k 通过 next[k] 回退——这和 KMP 匹配过程中的"失配回退"是完全相同的逻辑。

3. KMP 匹配过程

有了 next 数组，KMP 的匹配过程就很简单了：主串指针 i 永远不回退，只有模式串指针 j 在失配时通过 next[j] 回退。

import java.util.ArrayList;
import java.util.List;

/**
 * KMP 字符串匹配算法
 * 时间复杂度：O(n + m) — 主串和模式串各遍历一次
 * 空间复杂度：O(m) — next 数组
 */
public class KMPSearch {

    /**
     * 在 text 中查找 pattern 的所有出现位置
     */
    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (text == null || pattern == null || pattern.isEmpty()) {
            return result;
        }

        int n = text.length();
        int m = pattern.length();
        int[] next = buildNext(pattern);

        int i = 0;  // 主串指针
        int j = 0;  // 模式串指针

        while (i < n) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];  // 失配：模式串指针回退，主串指针不动
            }

            if (j == m) {
                result.add(i - m);  // 匹配成功
                j = next[j - 1] + 1;  // 继续查找下一个匹配（也可用 j = next[j-1] 再微调）
                // 简化写法：j = next[j - 1];  但需要 next 数组多算一位
                // 更通用的做法：
                j = next[j - 1];
                if (j >= 0 && pattern.charAt(j) == pattern.charAt(m - 1)) {
                    // 不需要额外处理，继续循环即可
                }
            }
        }
        return result;
    }

    /**
     * 构造 next 数组（KMP 优化版，也称为 nextval 数组）
     */
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;

        int k = -1;
        int j = 1;

        while (j < m) {
            if (k == -1 || pattern.charAt(k) == pattern.charAt(j - 1)) {
                k++;
                // 优化：如果 pattern[k] == pattern[j]，则 next[j] = next[k]
                // 因为如果 pattern[j] 失配，用 pattern[k] 也必然失配
                if (pattern.charAt(k) == pattern.charAt(j)) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
                j++;
            } else {
                k = next[k];
            }
        }
        return next;
    }
}

完整代码示例：

import java.util.ArrayList;
import java.util.List;

/**
 * KMP 字符串匹配算法（完整版）
 * 时间复杂度：O(n + m)
 * 空间复杂度：O(m)
 */
@SuppressWarnings("all")
public class KMPSearch {

    /**
     * 在 text 中查找 pattern 的所有出现位置
     * @param text    主串
     * @param pattern 模式串
     * @return 所有匹配的起始索引列表
     */
    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (text == null || pattern == null || pattern.isEmpty()) {
            return result;
        }

        int n = text.length();
        int m = pattern.length();
        if (m > n) return result;

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

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

            if (j == m) {
                result.add(i - m);
                j = next[j - 1];  // 利用 next 继续匹配
                if (j == -1) {
                    i++;  // next[j-1] = -1 时，主串也要前进
                    j = 0;
                }
            }
        }
        return result;
    }

    /**
     * 构造 next 数组
     */
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;

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

    public static void main(String[] args) {
        KMPSearch kmp = new KMPSearch();
        System.out.println(kmp.search("ABABCABAAABABCABAA", "ABABCABAA"));
        // 输出: [0, 9]
    }
}

下面用表格展示 KMP 的匹配过程：

KMP 的精髓：失配时，主串指针 i 不动，模式串指针 j 通过 next[j] 回退。这意味着主串中的每个字符最多被比较一次，因此总比较次数为 $O(n+m)$。

---

21.2.3 Boyer-Moore 算法

Boyer-Moore 算法（BM 算法）与 KMP 最大的不同在于：BM 从模式串的右端开始比较（从右往左），利用失配信息来跳过尽可能多的字符。

BM 算法使用两条启发式规则来决定模式串的滑动距离：

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

当从右向左比较时，遇到主串中的某个字符与模式串不匹配，这个主串字符称为"坏字符"。

• 如果坏字符在模式串中存在，则将模式串中最右边的该字符与坏字符对齐
• 如果坏字符在模式串中不存在，则将模式串整个滑过坏字符

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

当从右向左比较时，已经匹配成功的部分称为"好后缀"。好后缀规则利用这些已匹配的信息来决定滑动距离：

• 如果模式串中存在另一个与好后缀相同的子串，则将其与好后缀对齐
• 如果不存在，则寻找好后缀的最长前缀，使其与模式串的前缀对齐
• 如果都不存在，滑动 m 位（模式串长度）

实际应用：BM 算法通常同时使用坏字符规则和好后缀规则，取两者的较大滑动距离。在很多实际场景中，仅使用坏字符规则就已经效果很好。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Boyer-Moore 字符串匹配算法（简化版，仅使用坏字符规则）
 * 时间复杂度：最坏 O(n × m)，最佳 O(n/m)
 * 空间复杂度：O(字符集大小) — 坏字符表
 */
@SuppressWarnings("all")
public class BoyerMooreSearch {

    /**
     * 在 text 中查找 pattern 的所有出现位置
     */
    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (text == null || pattern == null || pattern.isEmpty()) {
            return result;
        }

        int n = text.length();
        int m = pattern.length();
        if (m > n) return result;

        // 构建坏字符表：记录每个字符在模式串中最右出现的位置
        Map<Character, Integer> badChar = buildBadCharTable(pattern);

        int i = 0;  // 主串中模式串的起始对齐位置
        while (i <= n - m) {
            int j = m - 1;  // 从模式串最右端开始比较

            // 从右向左比较
            while (j >= 0 && text.charAt(i + j) == pattern.charAt(j)) {
                j--;
            }

            if (j < 0) {
                // 全部匹配成功
                result.add(i);
                // 继续查找：滑动到下一个可能的位置
                char nextChar = (i + m < n) ? text.charAt(i + m) : '\0';
                int shift = m - badChar.getOrDefault(nextChar, -1);
                i += Math.max(1, shift);
            } else {
                // 失配：应用坏字符规则
                char bad = text.charAt(i + j);
                int bcShift = j - badChar.getOrDefault(bad, -1);
                i += Math.max(1, bcShift);  // 至少滑动 1 位
            }
        }
        return result;
    }

    /**
     * 构建坏字符表
     * 记录每个字符在模式串中最右出现的位置（不存在记为 -1）
     */
    private Map<Character, Integer> buildBadCharTable(String pattern) {
        Map<Character, Integer> table = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            table.put(pattern.charAt(i), i);
        }
        return table;
    }

    public static void main(String[] args) {
        BoyerMooreSearch bm = new BoyerMooreSearch();
        System.out.println(bm.search("HERE IS A SIMPLE EXAMPLE", "EXAMPLE"));
        // 输出: [17]
    }
}

算法分析：BM 算法在最坏情况下（如全相同字符）时间复杂度为 $O(n\times m)$，但在实际文本中，由于坏字符规则通常能跳过大量字符，平均性能远优于 KMP。许多文本编辑器的"查找"功能就是基于 BM 算法实现的。

---

21.2.4 Rabin-Karp 算法（滚动哈希）

Rabin-Karp 算法（RK 算法）采用了一种完全不同的思路：将字符串比较转化为数值比较。

核心思想：将长度为 m 的模式串和主串中每个长度为 m 的子串都映射为一个哈希值，如果哈希值相等，再进行精确比较。

滚动哈希：从子串 $s[i...i+m-1]$ 的哈希值，能在 $O(1)$ 时间内计算出子串 $s[i+\mathrm{1...}i+m]$ 的哈希值，这就是"滚动"的含义。

哈希函数设计：

$$H(s[i..i+m-1])=s[i]\times d^{m-1}+s[i+1]\times d^{m-2}+\cdots +s[i+m-1]\times d^0(\mathrm{mod}q)$$

其中 $d$ 为字符集大小（如 256），$q$ 为一个大质数（用于取模避免溢出）。

滚动递推公式：

$$H(s[i+\mathrm{1..}i+m])=(H(s[i..i+m-1])-s[i]\times d^{m-1})\times d+s[i+m](\mathrm{mod}q)$$

import java.util.ArrayList;
import java.util.List;

/**
 * Rabin-Karp 字符串匹配算法
 * 时间复杂度：平均 O(n + m)，最坏 O(n × m)（哈希冲突时）
 * 空间复杂度：O(1)
 */
@SuppressWarnings("all")
public class RabinKarpSearch {

    private static final int BASE = 256;      // 字符集大小
    private static final int MOD = 101;       // 大质数（简化演示，实际应取更大的质数如 10^9+7）

    /**
     * 在 text 中查找 pattern 的所有出现位置
     */
    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (text == null || pattern == null || pattern.isEmpty()) {
            return result;
        }

        int n = text.length();
        int m = pattern.length();
        if (m > n) return result;

        // 计算 d^(m-1) % MOD，用于滚动时去掉最高位
        int h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * BASE) % MOD;
        }

        // 计算模式串和主串第一个窗口的哈希值
        int patternHash = 0;
        int textHash = 0;
        for (int i = 0; i < m; i++) {
            patternHash = (patternHash * BASE + pattern.charAt(i)) % MOD;
            textHash = (textHash * BASE + text.charAt(i)) % MOD;
        }

        // 滑动窗口
        for (int i = 0; i <= n - m; i++) {
            // 哈希值相等时，进行精确比较（防止哈希冲突）
            if (patternHash == textHash) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    result.add(i);
                }
            }

            // 滚动哈希：计算下一个窗口的哈希值
            if (i < n - m) {
                textHash = ((textHash - text.charAt(i) * h) * BASE + text.charAt(i + m)) % MOD;
                // 处理负数
                if (textHash < 0) {
                    textHash += MOD;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        RabinKarpSearch rk = new RabinKarpSearch();
        System.out.println(rk.search("ABABCABAAABABCABAA", "ABABCABAA"));
        // 输出: [0, 9]
    }
}

算法分析：

• RK 算法的精髓在于滚动哈希——每次窗口滑动只需 $O(1)$ 时间更新哈希值
• 哈希冲突的概率取决于质数 $q$ 的选取，$q$ 越大冲突越少
• RK 算法特别适合多模式匹配场景：预处理所有模式串的哈希值，一次扫描主串即可

---

21.2.5 四种匹配算法对比

对比维度	暴力匹配	KMP	Boyer-Moore	Rabin-Karp
比较方向	从左到右	从左到右	从右到左	哈希比较
主串指针	回退	不回退	可跳过多位	滑动窗口
预处理	无	next 数组 O(m)	坏字符/好后缀表 O(m+σ)	模式串哈希 O(m)
最好时间	O(n)	O(n+m)	O(n/m)	O(n+m)
最坏时间	O(n×m)	O(n+m)	O(n×m)	O(n×m)
空间复杂度	O(1)	O(m)	O(m+σ)	O(1)
多模式匹配	不支持	不支持	不支持	天然支持
实际性能	差	稳定	通常最优	中等

选型建议：

• 通用场景：Boyer-Moore（实际性能最好，大多数编辑器使用）
• 理论保证：KMP（最坏 $O(n+m)$，稳定可靠）
• 多模式匹配：Rabin-Karp（哈希天然支持多模式）
• 简单场景：暴力法（代码简单，短字符串足够）

Java 标准库：String.indexOf() 在 Java 7+ 中对短模式串使用暴力匹配，对长模式串使用优化的算法。实际工程中，标准库的实现通常已经足够。

---

21.3 经典实战

21.3.1 最长回文子串 — LeetCode 5

问题描述：给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例：

输入：s = "babad"
输出："bab"（"aba" 同样是合法答案）

输入：s = "cbbd"
输出："bb"

1. 中心扩展法（O(n²)）

回文具有"对称性"——可以从中心向两边扩展来判断。每个字符（奇数长度回文）或每对相邻字符（偶数长度回文）都可能是回文的中心。

/**
 * 最长回文子串 — 中心扩展法（LeetCode 5）
 * 时间复杂度：O(n²) — 共 2n-1 个中心，每个中心最多扩展 n/2 次
 * 空间复杂度：O(1)
 */
public class LongestPalindrome {

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int start = 0, maxLen = 1;

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文：以 i 为中心
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度回文：以 i, i+1 为中心
            int len2 = expandAroundCenter(s, i, i + 1);

            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }

        return s.substring(start, start + maxLen);
    }

    /**
     * 从中心向两边扩展，返回回文长度
     * @param left  左中心
     * @param right 右中心（奇数长度时 left=right）
     */
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length()
                && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 退出时 left 和 right 各多走了一步
        return right - left - 1;
    }
}

2. Manacher 算法（O(n)）

Manacher 算法是求解最长回文子串的线性时间算法。其核心思想与 KMP 有异曲同工之妙——利用已知回文的信息，避免重复扩展。

关键概念：

• 回文半径：以位置 i 为中心的回文半径 p[i]，即回文串的半径长度（含中心）
• 最右回文边界：当前所有已探测回文中，右端最远的位置 maxRight
• 对称性：如果 i 在某个大回文的内部，那么 i 的回文半径可以利用其关于大回文中心的对称点 mirror 的信息

算法步骤：

1. 预处理：在字符串中插入特殊字符（如 #），将所有回文统一为奇数长度

   • "babad" → "#b#a#b#a#d#"

2. 利用对称性加速：

   • 当 i < maxRight 时，p[i] 至少等于 min(p[mirror], maxRight - i)
   • 然后尝试继续向外扩展

3. 更新边界：扩展完成后，更新 maxRight 和对应的中心 center

解读：p[5]=4 表示以 T[5]=‘b’ 为中心，回文半径为 4，对应原串中的 “bab”；p[3]=4 表示以 T[3]=‘a’ 为中心，回文半径为 4，对应 “aba”。最大回文半径为 4，对应原串中最长回文长度为 4-1=3。

/**
 * 最长回文子串 — Manacher 算法（LeetCode 5）
 * 时间复杂度：O(n) — 每个字符最多被访问常数次
 * 空间复杂度：O(n) — 预处理字符串和回文半径数组
 */
public class Manacher {

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        // ① 预处理：插入特殊字符，统一奇偶长度
        char[] t = new char[s.length() * 2 + 1];
        for (int i = 0; i < t.length; i++) {
            t[i] = (i % 2 == 0) ? '#' : s.charAt(i / 2);
        }

        // ② Manacher 核心算法
        int n = t.length;
        int[] p = new int[n];    // 回文半径数组
        int center = 0;          // 当前最右回文的中心
        int maxRight = 0;        // 当前最右回文的右边界

        int maxLen = 0;          // 最长回文半径
        int maxCenter = 0;       // 最长回文的中心

        for (int i = 0; i < n; i++) {
            if (i < maxRight) {
                // 利用对称性：p[i] 至少等于 min(p[mirror], maxRight - i)
                int mirror = 2 * center - i;
                p[i] = Math.min(p[mirror], maxRight - i);
            }

            // 尝试向外扩展
            while (i + p[i] < n && i - p[i] >= 0
                    && t[i + p[i]] == t[i - p[i]]) {
                p[i]++;
            }

            // 更新最右回文边界
            if (i + p[i] > maxRight) {
                maxRight = i + p[i];
                center = i;
            }

            // 记录最长回文
            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }

        // ③ 还原到原字符串
        // 在预处理串中，回文半径为 maxLen，对应原串长度为 maxLen - 1
        int start = (maxCenter - maxLen + 1) / 2;
        int len = maxLen - 1;
        return s.substring(start, start + len);
    }

    public static void main(String[] args) {
        Manacher m = new Manacher();
        System.out.println(m.longestPalindrome("babad"));  // bab 或 aba
        System.out.println(m.longestPalindrome("cbbd"));   // bb
    }
}

两种方法对比：

对比维度	中心扩展法	Manacher 算法
时间复杂度	O(n²)	O(n)
空间复杂度	O(1)	O(n)
代码复杂度	简单	较复杂
实际性能	n ≤ 1000 时足够	n ≤ 10^6 时必要

选型建议：

• 面试中写中心扩展法即可（代码简洁，容易理解）
• 如果面试官追问 O(n) 解法，再展示 Manacher

---

21.3.2 字符串转整数（atoi）— LeetCode 8

问题描述：实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。函数需要满足以下规则：

1. 读取并忽略前导空格
2. 检查下一个字符是 ‘+’ 还是 ‘-’
3. 读取数字字符，直到遇到非数字字符或字符串末尾
4. 将数字部分转换为整数，如果没有数字则返回 0
5. 整数范围限制在 $[-2^{31},2^{31}-1]$ 内，超出则截断

示例：

输入："42"           输出：42
输入："   -42"       输出：-42
输入："4193 with words"  输出：4193
输入："words and 987"    输出：0
输入："-91283472332"     输出：-2147483648（溢出截断）

这道题的难点不在于算法，而在于各种边界情况的处理——空格、正负号、非数字字符、溢出。

/**
 * 字符串转整数 atoi（LeetCode 8）
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
public class StringToInteger {

    public int myAtoi(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        int i = 0;
        int n = s.length();

        // ① 跳过前导空格
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }

        if (i == n) return 0;

        // ② 处理正负号
        int sign = 1;
        if (s.charAt(i) == '+') {
            i++;
        } else if (s.charAt(i) == '-') {
            sign = -1;
            i++;
        }

        // ③ 读取数字（关键：在累加过程中判断溢出）
        int result = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';

            // 溢出判断：result * 10 + digit > Integer.MAX_VALUE
            // 等价于 result > (MAX_VALUE - digit) / 10
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            result = result * 10 + digit;
            i++;
        }

        return sign * result;
    }

    public static void main(String[] args) {
        StringToInteger atoi = new StringToInteger();
        System.out.println(atoi.myAtoi("42"));             // 42
        System.out.println(atoi.myAtoi("   -42"));         // -42
        System.out.println(atoi.myAtoi("4193 with words")); // 4193
        System.out.println(atoi.myAtoi("words and 987"));  // 0
        System.out.println(atoi.myAtoi("-91283472332"));    // -2147483648
    }
}

溢出判断技巧：不要等到溢出后再判断（此时已经截断），而是在乘以 10 之前检查 result > (MAX_VALUE - digit) / 10。这样用 int 类型就能完成溢出判断，不需要 long。

---

21.3.3 字符串相乘 — LeetCode 43

问题描述：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也用字符串形式表示。不能使用任何标准库的大数类型或直接将输入转换为整数。

示例：

输入：num1 = "123", num2 = "456"
输出："56088"

这道题模拟手工乘法的过程：逐位相乘，然后处理进位。

/**
 * 字符串相乘（LeetCode 43）
 * 时间复杂度：O(m × n)
 * 空间复杂度：O(m + n) — 结果数组
 */
public class MultiplyStrings {

    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) return "0";
        if (num1.equals("0") || num2.equals("0")) return "0";

        int m = num1.length();
        int n = num2.length();

        // 结果最多 m + n 位
        int[] result = new int[m + n];

        // 从右向左，逐位相乘
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // 乘积放在 result[i + j + 1]（低位），进位放在 result[i + j]（高位）
                int sum = product + result[i + j + 1];
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }

        // 转为字符串，跳过前导零
        StringBuilder sb = new StringBuilder();
        for (int digit : result) {
            if (sb.length() == 0 && digit == 0) continue;  // 跳过前导零
            sb.append(digit);
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }

    public static void main(String[] args) {
        MultiplyStrings ms = new MultiplyStrings();
        System.out.println(ms.multiply("123", "456"));   // 56088
        System.out.println(ms.multiply("2", "3"));       // 6
        System.out.println(ms.multiply("0", "123"));     // 0
    }
}

关键洞察：num1[i] × num2[j] 的结果，其个位落在 result[i + j + 1]，十位落在 result[i + j]。这个位置关系是本算法的核心——它使得我们无需额外存储中间结果，直接在结果数组上累加即可。

---

21.3.4 最小覆盖子串 — LeetCode 76

问题描述：给你一个字符串 s 和一个字符串 t。返回 s 中涵盖 t 所有字符（包括重复字符）的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "aa"
输出：""

这是滑动窗口的经典应用。核心思路：维护一个窗口 [left, right)，右指针不断扩展窗口直到满足条件，然后左指针收缩窗口直到不满足条件——如此往复，记录最小的满足条件的窗口。

import java.util.HashMap;
import java.util.Map;

/**
 * 最小覆盖子串 — 滑动窗口（LeetCode 76）
 * 时间复杂度：O(n + m) — 两个指针各遍历一次
 * 空间复杂度：O(字符集大小)
 */
@SuppressWarnings("all")
public class MinimumWindowSubstring {

    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // ① 统计 t 中各字符的需求量
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // ② 滑动窗口
        int left = 0, right = 0;
        int valid = 0;                    // 满足需求的字符种类数
        Map<Character, Integer> window = new HashMap<>();

        int start = 0, minLen = Integer.MAX_VALUE;

        while (right < s.length()) {
            // 右指针扩展：加入字符
            char c = s.charAt(right);
            right++;

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 该字符已满足需求
                if (window.get(c).intValue() == need.get(c).intValue()) {
                    valid++;
                }
            }

            // 所有字符都已满足，开始收缩
            while (valid == need.size()) {
                // 更新最小窗口
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                // 左指针收缩：移除字符
                char d = s.charAt(left);
                left++;

                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;  // 不再满足需求
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    public static void main(String[] args) {
        MinimumWindowSubstring mws = new MinimumWindowSubstring();
        System.out.println(mws.minWindow("ADOBECODEBANC", "ABC"));  // BANC
        System.out.println(mws.minWindow("a", "aa"));               // (空)
    }
}

下面用表格展示滑动窗口的逐步过程：

滑动窗口的核心框架：

1. 用 need 哈希表记录目标字符的需求量
2. 用 window 哈希表记录窗口内字符的拥有量
3. 用 valid 计数器跟踪"已满足需求的字符种类数"
4. 右指针扩展 → 满足条件 → 左指针收缩 → 记录最优解 → 继续扩展

这个框架可以推广到所有滑动窗口类字符串问题：无重复字符最长子串（LeetCode 3）、找到字符串中所有字母异位词（LeetCode 438）等。

---

总结与预告

本章系统学习了字符串算法的完整体系：

• 21.1 问题引入：字符串匹配是字符串算法的核心问题，暴力法的痛点在于"主串指针回退导致重复比较"
• 21.2 四大匹配算法：

算法	核心思想	最坏时间	最佳时间	适用场景
暴力匹配	逐位比较	O(n×m)	O(n)	短字符串
KMP	next 数组 + 主串不回退	O(n+m)	O(n+m)	理论保证
Boyer-Moore	从右向左 + 坏字符/好后缀	O(n×m)	O(n/m)	实际最优
Rabin-Karp	滚动哈希	O(n×m)	O(n+m)	多模式匹配

• 21.3 四大经典实战：

问题	核心策略	时间复杂度	关键技巧
最长回文子串	中心扩展 / Manacher	O(n²) / O(n)	对称性、回文半径
字符串转整数	逐字符扫描 + 溢出判断	O(n)	乘 10 前判断溢出
字符串相乘	逐位相乘 + 进位	O(m×n)	位置映射 i+j, i+j+1
最小覆盖子串	滑动窗口	O(n+m)	need/window/valid 三变量

字符串算法的核心套路：

1. 字符串匹配：KMP 学会 next 数组的构造，BM 理解坏字符规则，RK 掌握滚动哈希
2. 回文问题：中心扩展是通用解法，Manacher 是进阶优化
3. 滑动窗口：need + window + valid 三变量框架，适用于所有"在 s 中找满足条件的子串"问题
4. 大数运算：用数组模拟手工计算，注意进位处理

字符串 vs 数组：字符串本质上是字符数组，但字符串算法有其独特性——字符集有限（通常为 ASCII 或 Unicode）、匹配操作频繁、哈希映射便捷。理解这些特性，才能选择最适合的算法。

下一章我们将进入位运算技巧专题——学习与、或、异或、移位等位运算操作，以及 BitMap、布隆过滤器等基于位运算的数据结构。位运算是算法中最"底层"的优化手段，掌握它能让你的代码在某些场景下快上数倍。

---

上篇：第二十章、回溯算法
下篇：第二十二章、位运算技巧