字符串算法 ⭐⭐⭐ 🔥

重要性：⭐⭐⭐ 重要
出现频率：🔥 中频（近3年出现8次，占比5%）
难度等级：中级到高级
前置知识：字符串基础操作、数组、哈希表
预计学习时长：3-4天

---

目录

• 算法原理
• 核心模板
• 使用场景识别指南
• 题型特征总结
• 解题思维技巧
• 字符串基础操作
• KMP算法
• 字符串哈希
• Trie树
• 易错点提醒
• 优化技巧
• 练习题推荐

---

算法原理

字符串算法是算法竞赛的重要组成部分，虽然在码蹄杯中占比不高（约5%），但一旦出现就是拉开差距的关键题。掌握字符串算法，你就能在关键时刻多拿一题，提升排名。

为什么字符串算法重要？

1. 拉开差距的关键

• 码蹄杯近3年统计：字符串算法占比5%
• T6-T8可能出现：KMP、字符串哈希、Trie树
• 掌握者少：很多选手不熟悉，容易拉开差距

2. 实际应用广泛

• 文本搜索：KMP算法
• 字符串匹配：字符串哈希
• 前缀匹配：Trie树
• 字符串处理：各种基础操作

3. 与其他算法结合

• 动态规划：最长公共子序列、编辑距离
• 哈希表：字符串去重、统计
• 双指针：滑动窗口、回文串

字符串算法的核心思想

字符串基础操作：拼接、截取、反转、比较
KMP算法：高效的字符串匹配，O(n+m)时间复杂度
字符串哈希：将字符串映射为数字，快速比较
Trie树：前缀树，高效的前缀匹配和字符串存储

---

核心模板

字符串基础操作模板

import java.util.*;

public class StringBasicTemplate {
    
    // 1. 字符串拼接（使用StringBuilder，避免创建大量临时对象）
    public String concatenate(String[] strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }
    
    // 2. 字符串反转
    public String reverse(String s) {
        // 方法1：使用StringBuilder（推荐）
        return new StringBuilder(s).reverse().toString();
        
        // 方法2：使用char数组（更灵活）
        // char[] chars = s.toCharArray();
        // int left = 0, right = chars.length - 1;
        // while (left < right) {
        //     char temp = chars[left];
        //     chars[left] = chars[right];
        //     chars[right] = temp;
        //     left++;
        //     right--;
        // }
        // return new String(chars);
    }
    
    // 3. 判断回文串
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    
    // 4. 字符串比较（字典序）
    public int compare(String s1, String s2) {
        return s1.compareTo(s2);  // 返回负数表示s1<s2，0表示相等，正数表示s1>s2
    }
    
    // 5. 字符串分割
    public String[] split(String s, String delimiter) {
        return s.split(delimiter);
    }
    
    // 6. 字符串替换
    public String replace(String s, String oldStr, String newStr) {
        return s.replace(oldStr, newStr);
    }
    
    // 7. 字符串转字符数组（频繁修改时使用）
    public char[] toCharArray(String s) {
        return s.toCharArray();
    }
    
    // 8. 字符数组转字符串
    public String fromCharArray(char[] chars) {
        return new String(chars);
    }
}

KMP算法模板

public class KMPTemplate {
    
    // KMP算法：在文本串text中查找模式串pattern的所有出现位置
    // 时间复杂度：O(n + m)，其中n是text长度，m是pattern长度
    // 空间复杂度：O(m)
    
    // 1. 构建next数组（最长公共前后缀）
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = 0;  // 第一个字符的最长公共前后缀长度为0
        
        int j = 0;  // j表示当前最长公共前后缀的长度
        for (int i = 1; i < m; i++) {
            // 如果不匹配，回退到next[j-1]
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 如果匹配，j++
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            next[i] = j;
        }
        
        return next;
    }

    
    // 2. KMP匹配（查找第一个匹配位置）
    public int kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0) return 0;
        if (n < m) return -1;
        
        int[] next = buildNext(pattern);
        
        int j = 0;  // pattern的指针
        for (int i = 0; i < n; i++) {  // text的指针
            // 如果不匹配，回退
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 如果匹配，j++
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 如果完全匹配，返回起始位置
            if (j == m) {
                return i - m + 1;
            }
        }
        
        return -1;  // 未找到
    }
    
    // 3. KMP匹配（查找所有匹配位置）
    public List<Integer> kmpSearchAll(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0 || n < m) return result;
        
        int[] next = buildNext(pattern);
        
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            if (j == m) {
                result.add(i - m + 1);  // 记录匹配位置
                j = next[j - 1];  // 继续查找下一个匹配
            }
        }
        
        return result;
    }
}

字符串哈希模板

public class StringHashTemplate {
    
    // 字符串哈希：将字符串映射为数字，快速比较两个字符串是否相等
    // 时间复杂度：预处理O(n)，查询O(1)
    // 空间复杂度：O(n)
    
    private static final long MOD = 1000000007;  // 模数
    private static final long BASE = 131;  // 进制（常用131或13331）
    
    // 1. 计算单个字符串的哈希值
    public long hash(String s) {
        long h = 0;
        for (int i = 0; i < s.length(); i++) {
            h = (h * BASE + s.charAt(i)) % MOD;
        }
        return h;
    }
    
    // 2. 预处理前缀哈希（支持快速查询任意子串的哈希值）
    private long[] prefixHash;  // prefixHash[i]表示s[0...i-1]的哈希值
    private long[] power;  // power[i]表示BASE^i
    
    public void buildPrefixHash(String s) {
        int n = s.length();
        prefixHash = new long[n + 1];
        power = new long[n + 1];
        
        power[0] = 1;
        for (int i = 1; i <= n; i++) {
            prefixHash[i] = (prefixHash[i - 1] * BASE + s.charAt(i - 1)) % MOD;
            power[i] = (power[i - 1] * BASE) % MOD;
        }
    }
    
    // 3. 查询子串s[left...right]的哈希值
    public long getSubstringHash(int left, int right) {
        // 注意：left和right是0-indexed
        long h = (prefixHash[right + 1] - prefixHash[left] * power[right - left + 1] % MOD + MOD) % MOD;
        return h;
    }
    
    // 4. 判断两个子串是否相等
    public boolean isEqual(int left1, int right1, int left2, int right2) {
        return getSubstringHash(left1, right1) == getSubstringHash(left2, right2);
    }
}

Trie树模板

public class TrieTemplate {
    
    // Trie树（前缀树）：高效的字符串存储和前缀匹配
    // 插入、查找、前缀匹配：O(m)，其中m是字符串长度
    // 空间复杂度：O(总字符数 × 字符集大小)
    
    // Trie节点定义
    class TrieNode {
        TrieNode[] children;  // 子节点数组（26个小写字母）
        boolean isEnd;  // 是否是单词结尾
        int count;  // 经过该节点的单词数量（可选）
        
        public TrieNode() {
            children = new TrieNode[26];  // 假设只有小写字母
            isEnd = false;
            count = 0;
        }
    }
    
    private TrieNode root;
    
    public TrieTemplate() {
        root = new TrieNode();
    }
    
    // 1. 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
            node.count++;  // 经过该节点的单词数+1
        }
        node.isEnd = true;  // 标记单词结尾
    }
    
    // 2. 查找单词是否存在
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEnd;  // 必须是单词结尾
    }
    
    // 3. 查找是否存在以prefix为前缀的单词
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;  // 只要能走到prefix的末尾即可
    }
    
    // 4. 删除单词
    public boolean delete(String word) {
        return deleteHelper(root, word, 0);
    }
    
    private boolean deleteHelper(TrieNode node, String word, int index) {
        if (index == word.length()) {
            if (!node.isEnd) {
                return false;  // 单词不存在
            }
            node.isEnd = false;  // 取消单词结尾标记
            return node.children.length == 0;  // 如果没有子节点，可以删除
        }
        
        int charIndex = word.charAt(index) - 'a';
        TrieNode child = node.children[charIndex];
        if (child == null) {
            return false;  // 单词不存在
        }
        
        boolean shouldDeleteChild = deleteHelper(child, word, index + 1);
        
        if (shouldDeleteChild) {
            node.children[charIndex] = null;  // 删除子节点
            return !node.isEnd && node.children.length == 0;
        }
        
        return false;
    }
    
    // 5. 统计以prefix为前缀的单词数量
    public int countWordsWithPrefix(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (node.children[index] == null) {
                return 0;
            }
            node = node.children[index];
        }
        return node.count;
    }
}

---

使用场景识别指南

什么时候用字符串算法？看这5个特征

特征1：题目中出现"字符串匹配"、"查找子串"关键词

• 示例：“在文本中查找模式串” → 用KMP算法
• 示例：“判断s2是否是s1的子串” → 用KMP算法或字符串哈希
• 示例：“查找所有匹配位置” → 用KMP算法

特征2：题目中出现"前缀"、“字典”、"单词搜索"关键词

• 示例：“判断是否存在以prefix开头的单词” → 用Trie树
• 示例：“实现字典的插入和查找” → 用Trie树
• 示例：“单词搜索II” → 用Trie树 + DFS

特征3：题目中出现"子串比较"、"重复子串"关键词

• 示例：“判断两个子串是否相等” → 用字符串哈希
• 示例：“查找最长重复子串” → 用字符串哈希 + 二分查找
• 示例：“判断字符串是否由重复子串构成” → 用字符串哈希或KMP

特征4：数据范围特点

• 示例：文本长度n ≤ 10^6，模式串长度m ≤ 10^3 → 用KMP（O(n+m)）
• 示例：字符串数量k ≤ 10^4，每个长度≤100 → 用Trie树存储
• 示例：需要查询10^5次子串是否相等 → 用字符串哈希预处理

特征5：暴力解法的时间复杂度

• 示例：暴力匹配O(n×m)，需要优化 → 用KMP优化到O(n+m)
• 示例：暴力比较子串O(n×m)，需要优化 → 用字符串哈希优化到O(1)
• 示例：暴力存储字符串O(总字符数)，需要优化 → 用Trie树共享前缀

快速判断流程图

题目特征 → 算法选择
├─ 字符串匹配、查找子串 → KMP算法
├─ 前缀匹配、字典操作 → Trie树
├─ 子串比较、重复子串 → 字符串哈希
├─ 回文串、反转 → 双指针
└─ 字符串拼接、修改 → StringBuilder

---

题型特征总结

字符串算法对应的题目特征

算法类型	关键词	典型题型	时间复杂度
KMP算法	“匹配”、“查找子串”、“模式串”	字符串匹配、重复子串判断	O(n+m)
字符串哈希	“子串比较”、“重复子串”、“最长公共子串”	快速子串比较、查找重复	预处理O(n)，查询O(1)
Trie树	“前缀”、“字典”、“单词搜索”	前缀匹配、字典实现、单词搜索	O(m)
双指针	“回文串”、“反转”、“滑动窗口”	回文判断、最长回文子串	O(n)
StringBuilder	“拼接”、“修改”、“构造”	字符串拼接、动态构造	O(n)

题目描述中的信号词

KMP算法信号词：

• “在文本中查找模式串”
• “判断s2是否是s1的子串”
• “查找所有匹配位置”
• “重复子串”
• “最小循环节”

字符串哈希信号词：

• “判断两个子串是否相等”
• “查找最长重复子串”
• “最长公共子串”
• “字符串去重”
• “快速比较”

Trie树信号词：

• “前缀匹配”
• “字典实现”
• “单词搜索”
• “自动补全”
• “最长公共前缀”

双指针信号词：

• “回文串”
• “反转字符串”
• “最长回文子串”
• “滑动窗口”
• “两端向中间”

---

解题思维技巧

从题目到字符串算法的思维路径（3步法）

第1步：判断是否需要字符串算法

• 检查点1：题目是否涉及字符串匹配、前缀匹配、子串比较？
• 检查点2：暴力解法的时间复杂度是否过高（如O(n×m)）？
• 检查点3：是否需要高效的字符串存储和查询？

第2步：选择具体的算法

• 情况A：字符串匹配、查找子串 → KMP算法
• 情况B：前缀匹配、字典操作 → Trie树
• 情况C：子串比较、重复子串 → 字符串哈希
• 情况D：回文串、反转 → 双指针
• 情况E：字符串拼接、修改 → StringBuilder

第3步：实现细节

• 注意点1：KMP的next数组构建要正确
• 注意点2：字符串哈希要选择合适的模数和进制
• 注意点3：Trie树要根据字符集大小调整children数组
• 注意点4：使用StringBuilder避免创建大量临时对象

竞赛思维技巧

1. 优先使用内置方法

• Java的String.indexOf()底层使用了优化的匹配算法
• 简单匹配可以直接用indexOf()，不必手写KMP
• 但复杂场景（如查找所有匹配位置）需要手写KMP

2. 字符串哈希的模数选择

• 常用模数：1000000007（10^9+7）、1000000009
• 常用进制：131、13331
• 双哈希：使用两个不同的模数和进制，降低冲突概率

3. Trie树的空间优化

• 如果字符集很大（如所有ASCII字符），使用HashMap代替数组
• 如果只需要判断前缀，不需要存储count

4. 字符串比较的优化

• 先比较长度，长度不同直接返回false
• 使用字符串哈希预处理，O(1)比较子串

5. 字符串拼接的优化

• 使用StringBuilder，避免创建大量临时String对象
• 预估容量：new StringBuilder(capacity)，减少扩容次数

避坑指南

❌ 错误做法1：使用String直接拼接

String result = "";
for (int i = 0; i < n; i++) {
    result += str[i];  // 每次拼接都创建新对象，O(n^2)
}

✅ 正确做法1：使用StringBuilder

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append(str[i]);  // O(n)
}
String result = sb.toString();

❌ 错误做法2：KMP的next数组下标错误

// 错误：next数组下标从1开始，容易越界
int[] next = new int[m + 1];

✅ 正确做法2：next数组下标从0开始

// 正确：next数组下标从0开始，与字符串下标一致
int[] next = new int[m];

❌ 错误做法3：字符串哈希溢出

// 错误：没有取模，可能溢出
long h = h * BASE + s.charAt(i);

✅ 正确做法3：每次运算都取模

// 正确：每次运算都取模，避免溢出
long h = (h * BASE + s.charAt(i)) % MOD;

❌ 错误做法4：Trie树的children数组大小错误

// 错误：字符集包含大小写字母，但只开了26个空间
TrieNode[] children = new TrieNode[26];

✅ 正确做法4：根据字符集大小调整

// 正确：大小写字母共52个，或使用HashMap
TrieNode[] children = new TrieNode[52];
// 或者使用HashMap
Map<Character, TrieNode> children = new HashMap<>();

---

字符串基础操作

算法原理

字符串基础操作是所有字符串算法的基础，包括拼接、截取、反转、比较等。虽然这些操作看似简单，但在竞赛中如果使用不当，会导致时间复杂度过高，甚至超时。

核心要点：

1. 使用StringBuilder拼接字符串：避免创建大量临时对象
2. 使用char[]进行频繁修改：比String更高效
3. 使用双指针处理回文串：O(n)时间复杂度
4. 使用compareTo()比较字典序：标准方法

典型例题1：反转字符串

题目：LeetCode 344 - 反转字符串（Easy）

题目描述：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入输出样例：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

数据范围：

• 1 ≤ s.length ≤ 10^5
• s[i] 都是 ASCII 码表中的可打印字符

题型识别：

• 关键词：“反转”
• 特征：原地修改，O(1)空间
• 算法：双指针

解题思路：

1. 使用双指针，left指向开头，right指向末尾
2. 交换left和right位置的字符
3. left右移，right左移，直到left >= right
4. 时间复杂度O(n)，空间复杂度O(1)

完整代码：

public class Solution {
    public void reverseString(char[] s) {
        // 双指针：left指向开头，right指向末尾
        int left = 0;
        int right = s.length - 1;
        
        // 当left < right时，交换并移动指针
        while (left < right) {
            // 交换s[left]和s[right]
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            
            // 移动指针
            left++;
            right--;
        }
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n是字符串长度。需要遍历一半的字符串。
• 空间复杂度：O(1)，只使用了常数个额外变量。

举一反三：

1. 变体题1：反转字符串中的单词

   • 题目：给定字符串"hello world"，反转为"world hello"
   • 解法：先反转整个字符串，再反转每个单词
   • 关键变化：需要识别单词边界

2. 变体题2：反转字符串的一部分

   • 题目：反转字符串s[left…right]
   • 解法：双指针，但起始位置是left和right
   • 关键变化：指针的初始位置不同

3. 变体题3：旋转字符串

   • 题目：将字符串"abcdef"旋转2位，变为"efabcd"
   • 解法：反转前n-k个字符，反转后k个字符，再反转整个字符串
   • 关键变化：需要分段反转

同类题型推荐：

• LeetCode 541 - 反转字符串II（Easy）
• LeetCode 557 - 反转字符串中的单词III（Easy）
• 码蹄集 MT1234 - 字符串反转（青铜）

---

典型例题2：验证回文串

题目：LeetCode 125 - 验证回文串（Easy）

题目描述：
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true；否则，返回 false。

输入输出样例：

输入：s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串

数据范围：

• 1 ≤ s.length ≤ 2 × 10^5
• s 仅由可打印的 ASCII 字符组成

题型识别：

• 关键词：“回文串”
• 特征：需要忽略非字母数字字符，忽略大小写
• 算法：双指针

解题思路：

1. 使用双指针，left指向开头，right指向末尾
2. 跳过非字母数字字符
3. 比较left和right位置的字符（忽略大小写）
4. 如果不相等，返回false；否则继续
5. 时间复杂度O(n)，空间复杂度O(1)

完整代码：

public class Solution {
    public boolean isPalindrome(String s) {
        // 双指针：left指向开头，right指向末尾
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            // 比较字符（忽略大小写）
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            
            // 移动指针
            left++;
            right--;
        }
        
        return true;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n是字符串长度。需要遍历一次字符串。
• 空间复杂度：O(1)，只使用了常数个额外变量。

举一反三：

1. 变体题1：验证回文串II

   • 题目：给定字符串，最多删除一个字符，判断是否能成为回文串
   • 解法：双指针，遇到不匹配时，尝试删除left或right，再判断
   • 关键变化：允许一次删除操作

2. 变体题2：最长回文子串

   • 题目：找到字符串中最长的回文子串
   • 解法：中心扩展法，以每个字符为中心向两边扩展
   • 关键变化：需要枚举所有可能的中心

3. 变体题3：回文链表

   • 题目：判断链表是否是回文
   • 解法：快慢指针找到中点，反转后半部分，再比较
   • 关键变化：数据结构从字符串变为链表

同类题型推荐：

• LeetCode 680 - 验证回文串II（Easy）
• LeetCode 5 - 最长回文子串（Medium）
• 码蹄集 MT1456 - 回文判断（白银）

---

KMP算法

算法原理

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在文本串中查找模式串。相比暴力匹配的O(n×m)时间复杂度，KMP算法可以在O(n+m)时间内完成匹配。

核心思想：

1. 利用已匹配的信息：当匹配失败时，不需要回退文本串的指针，只需要回退模式串的指针
2. next数组：记录模式串每个位置的最长公共前后缀长度
3. 避免重复比较：利用next数组跳过已经匹配过的部分

什么是最长公共前后缀？

• 前缀：不包含最后一个字符的所有子串
• 后缀：不包含第一个字符的所有子串
• 最长公共前后缀：既是前缀又是后缀的最长子串

示例：

• 字符串"ababa"的最长公共前后缀是"aba"（长度为3）
• 字符串"aaaa"的最长公共前后缀是"aaa"（长度为3）

KMP算法的两个步骤：

1. 构建next数组：预处理模式串，计算每个位置的最长公共前后缀长度
2. 匹配：利用next数组进行高效匹配

典型例题3：实现strStr()

题目：LeetCode 28 - 找出字符串中第一个匹配项的下标（Easy）

题目描述：
给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

输入输出样例：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0。

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1。

数据范围：

• 1 ≤ haystack.length, needle.length ≤ 10^4
• haystack 和 needle 仅由小写英文字符组成

题型识别：

• 关键词：“字符串匹配”、“查找子串”
• 特征：在文本串中查找模式串
• 算法：KMP算法

解题思路：

1. 构建needle的next数组
2. 使用KMP算法在haystack中查找needle
3. 找到第一个匹配位置就返回
4. 时间复杂度O(n+m)，空间复杂度O(m)

完整代码：

public class Solution {
    // KMP算法：在haystack中查找needle的第一个匹配位置
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        
        // 特殊情况处理
        if (m == 0) return 0;
        if (n < m) return -1;
        
        // 构建next数组
        int[] next = buildNext(needle);
        
        // KMP匹配
        int j = 0;  // needle的指针
        for (int i = 0; i < n; i++) {  // haystack的指针
            // 如果不匹配，回退needle的指针
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            
            // 如果匹配，needle的指针前进
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            
            // 如果完全匹配，返回起始位置
            if (j == m) {
                return i - m + 1;
            }
        }
        
        return -1;  // 未找到
    }
    
    // 构建next数组（最长公共前后缀）
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = 0;  // 第一个字符的最长公共前后缀长度为0
        
        int j = 0;  // j表示当前最长公共前后缀的长度
        for (int i = 1; i < m; i++) {
            // 如果不匹配，回退到next[j-1]
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 如果匹配，j++
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            next[i] = j;
        }
        
        return next;
    }
}

复杂度分析：

• 时间复杂度：O(n+m)，其中n是haystack长度，m是needle长度。构建next数组O(m)，匹配O(n)。
• 空间复杂度：O(m)，需要存储next数组。

举一反三：

1. 变体题1：查找所有匹配位置

   • 题目：找到needle在haystack中的所有匹配位置
   • 解法：KMP匹配，找到一个匹配后继续查找
   • 关键变化：找到匹配后不返回，而是记录位置并继续

2. 变体题2：重复的子字符串

   • 题目：判断字符串是否由重复的子串构成
   • 解法：如果s由重复子串构成，则s的最长公共前后缀长度为len - 最小循环节长度
   • 关键变化：利用KMP的next数组判断循环节

3. 变体题3：最短回文串

   • 题目：在字符串前面添加最少的字符，使其成为回文串
   • 解法：将s和reverse(s)拼接，用KMP找最长公共前后缀
   • 关键变化：结合字符串反转和KMP

同类题型推荐：

• LeetCode 459 - 重复的子字符串（Easy）
• LeetCode 214 - 最短回文串（Hard）
• 码蹄集 MT1678 - 字符串匹配（黄金）

---

典型例题4：重复的子字符串

题目：LeetCode 459 - 重复的子字符串（Easy）

题目描述：
给定一个非空的字符串 s，检查是否可以通过由它的一个子串重复多次构成。

输入输出样例：

输入：s = "abab"
输出：true
解释：可由子串 "ab" 重复两次构成。

输入：s = "aba"
输出：false

输入：s = "abcabcabcabc"
输出：true
解释：可由子串 "abc" 重复四次构成。

数据范围：

• 1 ≤ s.length ≤ 10^4
• s 由小写英文字母组成

题型识别：

• 关键词：“重复子串”
• 特征：判断字符串是否由重复的子串构成
• 算法：KMP算法（利用next数组）

解题思路：

1. 如果字符串s由重复子串构成，那么s的长度一定是最小循环节长度的倍数
2. 利用KMP的next数组，next[n-1]表示s的最长公共前后缀长度
3. 如果n % (n - next[n-1]) == 0，则s由重复子串构成
4. 最小循环节长度 = n - next[n-1]
5. 时间复杂度O(n)，空间复杂度O(n)

完整代码：

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        
        // 构建next数组
        int[] next = buildNext(s);
        
        // 如果next[n-1] > 0，说明存在公共前后缀
        // 如果n % (n - next[n-1]) == 0，说明可以由重复子串构成
        if (next[n - 1] > 0 && n % (n - next[n - 1]) == 0) {
            return true;
        }
        
        return false;
    }
    
    // 构建next数组
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = 0;
        
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            next[i] = j;
        }
        
        return next;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n是字符串长度。构建next数组需要O(n)时间。
• 空间复杂度：O(n)，需要存储next数组。

举一反三：

1. 变体题1：最小循环节

   • 题目：找到字符串的最小循环节
   • 解法：最小循环节长度 = n - next[n-1]
   • 关键变化：不仅判断是否存在，还要找到最小循环节

2. 变体题2：重复K次的子串

   • 题目：判断字符串是否由某个子串重复K次构成
   • 解法：检查n % k == 0，且s[0…n/k-1]重复k次等于s
   • 关键变化：指定重复次数

3. 变体题3：最长重复子串

   • 题目：找到字符串中最长的重复子串
   • 解法：后缀数组或字符串哈希 + 二分查找
   • 关键变化：从判断是否重复变为找最长重复

同类题型推荐：

• LeetCode 686 - 重复叠加字符串匹配（Medium）
• 码蹄集 MT1789 - 循环节判断（黄金）

---

字符串哈希

算法原理

字符串哈希是一种将字符串映射为数字的技术，可以在O(1)时间内比较两个子串是否相等。它的核心思想是将字符串看作一个P进制数，然后对一个大质数M取模。

核心思想：

1. 将字符串看作P进制数：每个字符对应一个数字，整个字符串是一个P进制数
2. 取模避免溢出：对大质数M取模，避免数字过大
3. 前缀哈希：预处理所有前缀的哈希值，快速查询任意子串的哈希值

哈希函数：

hash(s) = (s[0] * P^(n-1) + s[1] * P^(n-2) + ... + s[n-1] * P^0) % M

常用参数：

• P（进制）：131、13331（经验值，冲突概率低）
• M（模数）：10^9+7、109+9（大质数）

优点：

• 查询子串哈希值：O(1)
• 比较两个子串是否相等：O(1)

缺点：

• 存在哈希冲突（概率很小）
• 不能判断字典序大小

典型例题5：最长重复子串

题目：LeetCode 1044 - 最长重复子串（Hard）

题目描述：
给你一个字符串 s，考虑其所有重复子串：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之处可能存在重叠。

返回任意一个最长的重复子串。如果 s 不含重复子串，那么答案为 “”。

输入输出样例：

输入：s = "banana"
输出："ana"

输入：s = "abcd"
输出：""

数据范围：

• 2 ≤ s.length ≤ 3 × 10^4
• s 由小写英文字母组成

题型识别：

• 关键词：“重复子串”、“最长”
• 特征：需要快速比较大量子串
• 算法：字符串哈希 + 二分查找

解题思路：

1. 二分查找最长重复子串的长度len
2. 对于每个长度len，使用字符串哈希判断是否存在重复子串
3. 将所有长度为len的子串的哈希值存入HashSet
4. 如果某个子串的哈希值已经存在，说明找到了重复子串
5. 时间复杂度O(n log n)，空间复杂度O(n)

完整代码：

public class Solution {
    private static final long MOD = 1000000007;
    private static final long BASE = 131;
    
    public String longestDupSubstring(String s) {
        int n = s.length();
        
        // 二分查找最长重复子串的长度
        int left = 1, right = n - 1;
        int maxLen = 0;
        int maxStart = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int start = search(s, mid);
            
            if (start != -1) {
                // 存在长度为mid的重复子串
                maxLen = mid;
                maxStart = start;
                left = mid + 1;  // 尝试更长的长度
            } else {
                right = mid - 1;  // 尝试更短的长度
            }
        }
        
        return maxLen == 0 ? "" : s.substring(maxStart, maxStart + maxLen);
    }
    
    // 判断是否存在长度为len的重复子串，返回起始位置（不存在返回-1）
    private int search(String s, int len) {
        int n = s.length();
        
        // 预处理：计算BASE^len
        long pow = 1;
        for (int i = 0; i < len; i++) {
            pow = (pow * BASE) % MOD;
        }
        
        // 计算第一个子串的哈希值
        long hash = 0;
        for (int i = 0; i < len; i++) {
            hash = (hash * BASE + s.charAt(i)) % MOD;
        }
        
        // 使用HashSet存储所有子串的哈希值
        Set<Long> seen = new HashSet<>();
        seen.add(hash);
        
        // 滑动窗口：计算所有长度为len的子串的哈希值
        for (int i = 1; i <= n - len; i++) {
            // 移除最左边的字符，添加最右边的字符
            hash = (hash * BASE - s.charAt(i - 1) * pow % MOD + MOD) % MOD;
            hash = (hash + s.charAt(i + len - 1)) % MOD;
            
            // 如果哈希值已经存在，说明找到了重复子串
            if (seen.contains(hash)) {
                return i;  // 返回起始位置
            }
            
            seen.add(hash);
        }
        
        return -1;  // 不存在长度为len的重复子串
    }
}

复杂度分析：

• 时间复杂度：O(n log n)，其中n是字符串长度。二分查找O(log n)，每次查找需要O(n)时间。
• 空间复杂度：O(n)，需要存储所有子串的哈希值。

举一反三：

1. 变体题1：最长公共子串

   • 题目：找到两个字符串的最长公共子串
   • 解法：二分查找长度，用字符串哈希判断是否存在公共子串
   • 关键变化：需要同时处理两个字符串

2. 变体题2：查找重复的DNA序列

   • 题目：找到所有长度为10的重复DNA序列
   • 解法：字符串哈希，将所有长度为10的子串的哈希值存入HashSet
   • 关键变化：固定长度，不需要二分查找

3. 变体题3：判断子串是否相等

   • 题目：给定多次查询，判断s[l1…r1]和s[l2…r2]是否相等
   • 解法：预处理前缀哈希，O(1)查询子串哈希值
   • 关键变化：多次查询，需要预处理

同类题型推荐：

• LeetCode 187 - 重复的DNA序列（Medium）
• LeetCode 718 - 最长重复子数组（Medium）
• 码蹄集 MT1890 - 子串比较（钻石）

---

典型例题6：重复的DNA序列

题目：LeetCode 187 - 重复的DNA序列（Medium）

题目描述：
DNA序列由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’。

例如，“ACGAATTCCG” 是一个 DNA序列。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s，返回所有在 DNA 分子中出现不止一次的长度为 10 的序列（子字符串）。你可以按任意顺序返回答案。

输入输出样例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

数据范围：

• 1 ≤ s.length ≤ 10^5
• s[i] 为 ‘A’、‘C’、‘G’ 或 ‘T’

题型识别：

• 关键词：“重复序列”、“长度为10”
• 特征：固定长度的子串，需要快速判断重复
• 算法：字符串哈希或滑动窗口

解题思路：

1. 使用滑动窗口遍历所有长度为10的子串
2. 使用HashMap记录每个子串出现的次数
3. 将出现次数≥2的子串加入结果
4. 时间复杂度O(n)，空间复杂度O(n)

完整代码：

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();
        
        // 如果长度小于10，不可能有重复序列
        if (n < 10) {
            return result;
        }
        
        // 使用HashMap记录每个子串出现的次数
        Map<String, Integer> count = new HashMap<>();
        
        // 滑动窗口：遍历所有长度为10的子串
        for (int i = 0; i <= n - 10; i++) {
            String substring = s.substring(i, i + 10);
            count.put(substring, count.getOrDefault(substring, 0) + 1);
            
            // 如果出现次数恰好为2，加入结果（避免重复添加）
            if (count.get(substring) == 2) {
                result.add(substring);
            }
        }
        
        return result;
    }
}

优化版本（使用字符串哈希）：

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();
        
        if (n < 10) {
            return result;
        }
        
        // 将字符映射为数字：A->0, C->1, G->2, T->3
        Map<Character, Integer> charToNum = new HashMap<>();
        charToNum.put('A', 0);
        charToNum.put('C', 1);
        charToNum.put('G', 2);
        charToNum.put('T', 3);
        
        // 使用HashMap记录每个哈希值出现的次数
        Map<Integer, Integer> count = new HashMap<>();
        
        // 计算第一个子串的哈希值（使用4进制）
        int hash = 0;
        for (int i = 0; i < 10; i++) {
            hash = (hash << 2) | charToNum.get(s.charAt(i));  // 左移2位相当于乘以4
        }
        count.put(hash, 1);
        
        // 滑动窗口：计算所有长度为10的子串的哈希值
        int mask = (1 << 20) - 1;  // 保留低20位（10个字符，每个2位）
        for (int i = 1; i <= n - 10; i++) {
            // 移除最左边的字符，添加最右边的字符
            hash = ((hash << 2) | charToNum.get(s.charAt(i + 9))) & mask;
            
            count.put(hash, count.getOrDefault(hash, 0) + 1);
            
            // 如果出现次数恰好为2，加入结果
            if (count.get(hash) == 2) {
                result.add(s.substring(i, i + 10));
            }
        }
        
        return result;
    }
}

复杂度分析：

• 时间复杂度：O(n)，其中n是字符串长度。需要遍历一次字符串。
• 空间复杂度：O(n)，需要存储所有子串的哈希值。

举一反三：

1. 变体题1：查找长度为K的重复子串

   • 题目：将长度10改为任意长度K
   • 解法：滑动窗口，窗口大小为K
   • 关键变化：窗口大小可变

2. 变体题2：查找出现次数≥M的子串

   • 题目：将出现次数≥2改为≥M
   • 解法：HashMap记录次数，筛选次数≥M的子串
   • 关键变化：出现次数阈值可变

3. 变体题3：查找所有不同的重复子串

   • 题目：不限制长度，找到所有重复的子串
   • 解法：枚举所有可能的长度，使用字符串哈希判断
   • 关键变化：需要枚举长度

同类题型推荐：

• LeetCode 1044 - 最长重复子串（Hard）
• 码蹄集 MT1901 - DNA序列分析（黄金）

---

Trie树

算法原理

Trie树（前缀树）是一种树形数据结构，用于高效地存储和检索字符串集合。它的核心思想是利用字符串的公共前缀来减少存储空间和查询时间。

核心思想：

1. 共享前缀：相同前缀的字符串共享同一条路径
2. 树形结构：每个节点代表一个字符，从根到叶子的路径代表一个字符串
3. 快速查询：插入、查找、前缀匹配都是O(m)，其中m是字符串长度

Trie树的特点：

• 根节点不包含字符，其他节点包含一个字符
• 从根节点到某一节点的路径上的字符连接起来，就是该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

应用场景：

• 字典实现
• 自动补全
• 拼写检查
• 前缀匹配
• 单词搜索

典型例题7：实现Trie（前缀树）

题目：LeetCode 208 - 实现Trie（前缀树）（Medium）

题目描述：
Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true；否则，返回 false。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

输入输出样例：

输入：
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出：
[null, null, true, false, true, null, true]

解释：
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

数据范围：

• 1 ≤ word.length, prefix.length ≤ 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数总计不超过 3 × 10^4 次

题型识别：

• 关键词：“前缀树”、“字典”、“前缀匹配”
• 特征：需要高效的插入、查找、前缀匹配
• 算法：Trie树

解题思路：

1. 定义TrieNode类，包含children数组和isEnd标志
2. insert：从根节点开始，逐个字符插入，不存在则创建新节点
3. search：从根节点开始，逐个字符查找，最后检查isEnd
4. startsWith：从根节点开始，逐个字符查找，不需要检查isEnd
5. 时间复杂度O(m)，空间复杂度O(总字符数 × 26)

完整代码：

class Trie {
    // Trie节点定义
    class TrieNode {
        TrieNode[] children;  // 子节点数组（26个小写字母）
        boolean isEnd;  // 是否是单词结尾
        
        public TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }
    
    private TrieNode root;
    
    // 初始化Trie树
    public Trie() {
        root = new TrieNode();
    }
    
    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        
        // 逐个字符插入
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            
            // 如果子节点不存在，创建新节点
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            
            // 移动到子节点
            node = node.children[index];
        }
        
        // 标记单词结尾
        node.isEnd = true;
    }
    
    // 查找单词是否存在
    public boolean search(String word) {
        TrieNode node = root;
        
        // 逐个字符查找
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            
            // 如果子节点不存在，返回false
            if (node.children[index] == null) {
                return false;
            }
            
            // 移动到子节点
            node = node.children[index];
        }
        
        // 必须是单词结尾
        return node.isEnd;
    }
    
    // 查找是否存在以prefix为前缀的单词
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        
        // 逐个字符查找
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            
            // 如果子节点不存在，返回false
            if (node.children[index] == null) {
                return false;
            }
            
            // 移动到子节点
            node = node.children[index];
        }
        
        // 只要能走到prefix的末尾即可
        return true;
    }
}

复杂度分析：

• 时间复杂度：
  • insert：O(m)，其中m是单词长度
  • search：O(m)
  • startsWith：O(m)
• 空间复杂度：O(总字符数 × 26)，最坏情况下每个字符都需要一个节点

举一反三：

1. 变体题1：添加与搜索单词（支持通配符）

   • 题目：支持’.'通配符，可以匹配任意字符
   • 解法：在search时，遇到’.'需要尝试所有子节点
   • 关键变化：需要递归处理通配符

2. 变体题2：单词搜索II

   • 题目：在二维网格中查找所有存在于字典中的单词
   • 解法：Trie树 + DFS，在DFS过程中同时遍历Trie树
   • 关键变化：结合DFS和Trie树

3. 变体题3：最长公共前缀

   • 题目：找到字符串数组的最长公共前缀
   • 解法：将所有字符串插入Trie树，找到第一个分叉点
   • 关键变化：利用Trie树的结构特性

同类题型推荐：

• LeetCode 211 - 添加与搜索单词（Medium）
• LeetCode 212 - 单词搜索II（Hard）
• 码蹄集 MT2012 - 字典树应用（钻石）

---

典型例题8：单词搜索II

题目：LeetCode 212 - 单词搜索II（Hard）

题目描述：
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

输入输出样例：

输入：
board = [["o","a","a","n"],
         ["e","t","a","e"],
         ["i","h","k","r"],
         ["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

输入：
board = [["a","b"],["c","d"]]
words = ["abcb"]
输出：[]

数据范围：

• m == board.length
• n == board[i].length
• 1 ≤ m, n ≤ 12
• board[i][j] 是一个小写英文字母
• 1 ≤ words.length ≤ 3 × 10^4
• 1 ≤ words[i].length ≤ 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

题型识别：

• 关键词：“单词搜索”、“字典”、“网格”
• 特征：在网格中查找多个单词，需要高效的字典查询
• 算法：Trie树 + DFS

解题思路：

1. 将所有单词插入Trie树
2. 遍历网格的每个位置，从该位置开始DFS
3. DFS过程中同时遍历Trie树，如果当前字符不在Trie树中，剪枝
4. 如果到达Trie树的单词结尾，将单词加入结果
5. 时间复杂度O(m×n×4^L)，其中L是单词最大长度
6. 空间复杂度O(总字符数)

完整代码：

class Solution {
    // Trie节点定义
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;  // 如果是单词结尾，存储单词
    }
    
    private TrieNode root = new TrieNode();
    private List<String> result = new ArrayList<>();
    
    public List<String> findWords(char[][] board, String[] words) {
        // 1. 构建Trie树
        for (String word : words) {
            insert(word);
        }
        
        // 2. 遍历网格，从每个位置开始DFS
        int m = board.length;
        int n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root);
            }
        }
        
        return result;
    }
    
    // 插入单词到Trie树
    private void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.word = word;  // 存储单词
    }
    
    // DFS搜索
    private void dfs(char[][] board, int i, int j, TrieNode node) {
        // 边界检查
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        
        char c = board[i][j];
        
        // 如果已访问或不在Trie树中，剪枝
        if (c == '#' || node.children[c - 'a'] == null) {
            return;
        }
        
        // 移动到Trie树的下一个节点
        node = node.children[c - 'a'];
        
        // 如果找到单词，加入结果
        if (node.word != null) {
            result.add(node.word);
            node.word = null;  // 避免重复添加
        }
        
        // 标记当前位置已访问
        board[i][j] = '#';
        
        // 向四个方向DFS
        dfs(board, i - 1, j, node);  // 上
        dfs(board, i + 1, j, node);  // 下
        dfs(board, i, j - 1, node);  // 左
        dfs(board, i, j + 1, node);  // 右
        
        // 恢复当前位置（回溯）
        board[i][j] = c;
    }
}

复杂度分析：

• 时间复杂度：O(m×n×4^L)，其中m和n是网格大小，L是单词最大长度。最坏情况下需要遍历所有可能的路径。
• 空间复杂度：O(总字符数)，需要存储Trie树。

举一反三：

1. 变体题1：单词搜索I

   • 题目：在网格中查找单个单词
   • 解法：DFS，不需要Trie树
   • 关键变化：只查找一个单词，不需要字典

2. 变体题2：最长单词

   • 题目：找到网格中能构成的最长单词
   • 解法：Trie树 + DFS，记录最长单词
   • 关键变化：需要记录最长单词

3. 变体题3：单词接龙

   • 题目：从起始单词变换到目标单词，每次只能改变一个字母
   • 解法：BFS + Trie树，Trie树用于快速判断单词是否存在
   • 关键变化：从网格搜索变为单词变换

同类题型推荐：

• LeetCode 79 - 单词搜索（Medium）
• LeetCode 720 - 词典中最长的单词（Medium）
• 码蹄集 MT2123 - 单词迷宫（星耀）

---

易错点提醒

1. 字符串拼接性能问题

错误示例：

String result = "";
for (int i = 0; i < n; i++) {
    result += str[i];  // 每次拼接都创建新对象，O(n^2)
}

正确做法：

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append(str[i]);  // O(n)
}
String result = sb.toString();

原因：String是不可变对象，每次拼接都会创建新对象，导致时间复杂度为O(n^2)。StringBuilder是可变对象，拼接时不创建新对象，时间复杂度为O(n)。

---

2. KMP的next数组下标错误

错误示例：

// 错误：next数组下标从1开始，容易越界
int[] next = new int[m + 1];
next[1] = 0;
for (int i = 2; i <= m; i++) {
    // ...
}

正确做法：

// 正确：next数组下标从0开始，与字符串下标一致
int[] next = new int[m];
next[0] = 0;
for (int i = 1; i < m; i++) {
    // ...
}

原因：Java字符串下标从0开始，next数组也应该从0开始，保持一致性，避免下标错误。

---

3. 字符串哈希溢出

错误示例：

// 错误：没有取模，可能溢出
long h = h * BASE + s.charAt(i);

正确做法：

// 正确：每次运算都取模，避免溢出
long h = (h * BASE + s.charAt(i)) % MOD;

原因：字符串哈希的值可能非常大，超过long的范围，需要每次运算都取模。

---

4. 字符串哈希的减法取模

错误示例：

// 错误：减法可能产生负数
long h = (hash - s.charAt(i) * pow) % MOD;

正确做法：

// 正确：减法后加MOD再取模，确保结果为正
long h = (hash - s.charAt(i) * pow % MOD + MOD) % MOD;

原因：减法可能产生负数，需要加MOD再取模，确保结果为正数。

---

5. Trie树的children数组大小

错误示例：

// 错误：字符集包含大小写字母，但只开了26个空间
TrieNode[] children = new TrieNode[26];
int index = c - 'a';  // 大写字母会导致下标错误

正确做法：

// 方法1：根据字符集大小调整
TrieNode[] children = new TrieNode[52];  // 大小写字母共52个
int index = c >= 'a' ? c - 'a' : c - 'A' + 26;

// 方法2：使用HashMap（推荐，更灵活）
Map<Character, TrieNode> children = new HashMap<>();

原因：需要根据字符集大小调整children数组的大小，或使用HashMap更灵活。

---

6. 字符串比较使用==

错误示例：

// 错误：==比较的是引用，不是内容
if (s1 == s2) {
    // ...
}

正确做法：

// 正确：使用equals()比较内容
if (s1.equals(s2)) {
    // ...
}

原因：==比较的是引用（内存地址），equals()比较的是内容。

---

7. 字符串截取的边界

错误示例：

// 错误：substring的第二个参数是结束位置（不包含）
String sub = s.substring(i, j);  // 包含s[i]，不包含s[j]

正确理解：

// 正确：substring(i, j)返回s[i...j-1]
String sub = s.substring(i, j);  // 返回s[i...j-1]
String sub = s.substring(i, i + len);  // 返回长度为len的子串

原因：substring的第二个参数是结束位置（不包含），容易混淆。

---

8. 字符数组和字符串的转换

错误示例：

// 错误：char[]不能直接用+拼接
char[] chars = {'a', 'b', 'c'};
String s = chars + "";  // 错误，输出的是地址

正确做法：

// 正确：使用String构造函数
char[] chars = {'a', 'b', 'c'};
String s = new String(chars);

// 或者使用String.valueOf()
String s = String.valueOf(chars);

原因：char[]不能直接用+拼接，需要使用String构造函数或valueOf()方法。

---

9. KMP匹配时的指针回退

错误示例：

// 错误：回退到next[j]，应该回退到next[j-1]
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
    j = next[j];  // 错误
}

正确做法：

// 正确：回退到next[j-1]
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
    j = next[j - 1];  // 正确
}

原因：next[j]表示pattern[0…j]的最长公共前后缀长度，当pattern[j]不匹配时，应该回退到next[j-1]。

---

10. Trie树删除节点的判断

错误示例：

// 错误：删除节点时没有检查是否有其他单词经过
if (!node.isEnd) {
    node.children[index] = null;  // 可能删除了其他单词的路径
}

正确做法：

// 正确：只有当节点没有子节点且不是其他单词的结尾时才删除
if (!node.isEnd && node.children.length == 0) {
    node.children[index] = null;
}

原因：删除节点时需要检查是否有其他单词经过该节点，避免误删。

---

优化技巧

1. 字符串哈希的双哈希

问题：单哈希可能存在冲突，导致误判。

优化方案：使用两个不同的模数和进制，同时计算两个哈希值。

public class DoubleHash {
    private static final long MOD1 = 1000000007;
    private static final long MOD2 = 1000000009;
    private static final long BASE1 = 131;
    private static final long BASE2 = 13331;
    
    private long[] hash1, hash2;
    private long[] pow1, pow2;
    
    public void buildHash(String s) {
        int n = s.length();
        hash1 = new long[n + 1];
        hash2 = new long[n + 1];
        pow1 = new long[n + 1];
        pow2 = new long[n + 1];
        
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            hash1[i] = (hash1[i - 1] * BASE1 + s.charAt(i - 1)) % MOD1;
            hash2[i] = (hash2[i - 1] * BASE2 + s.charAt(i - 1)) % MOD2;
            pow1[i] = (pow1[i - 1] * BASE1) % MOD1;
            pow2[i] = (pow2[i - 1] * BASE2) % MOD2;
        }
    }
    
    // 查询子串s[left...right]的双哈希值
    public long[] getHash(int left, int right) {
        long h1 = (hash1[right + 1] - hash1[left] * pow1[right - left + 1] % MOD1 + MOD1) % MOD1;
        long h2 = (hash2[right + 1] - hash2[left] * pow2[right - left + 1] % MOD2 + MOD2) % MOD2;
        return new long[]{h1, h2};
    }
}

效果：双哈希的冲突概率极低，几乎可以忽略。

---

2. Trie树的空间优化

问题：Trie树的空间复杂度较高，尤其是字符集很大时。

优化方案1：使用HashMap代替数组

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

效果：只存储实际存在的子节点，节省空间。

优化方案2：压缩路径（Radix Tree）

class RadixNode {
    Map<String, RadixNode> children = new HashMap<>();
    boolean isEnd = false;
}

效果：将只有一个子节点的路径压缩为一条边，节省空间。

---

3. KMP的优化next数组

问题：标准KMP的next数组在某些情况下会导致多余的回退。

优化方案：优化next数组，跳过相同字符的回退。

private int[] buildNextOptimized(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = 0;
    
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        
        // 优化：如果pattern[i+1] == pattern[next[i]]，跳过
        if (i + 1 < m && pattern.charAt(i + 1) == pattern.charAt(j)) {
            next[i] = next[j - 1];
        } else {
            next[i] = j;
        }
    }
    
    return next;
}

效果：减少不必要的回退，提高匹配效率。

---

4. 字符串哈希的滚动哈希

问题：每次计算子串哈希值需要O(m)时间。

优化方案：使用滚动哈希，O(1)时间更新哈希值。

// 滑动窗口：从s[i...i+len-1]移动到s[i+1...i+len]
long newHash = (oldHash * BASE - s.charAt(i) * pow % MOD + MOD) % MOD;
newHash = (newHash + s.charAt(i + len)) % MOD;

效果：将时间复杂度从O(m)降低到O(1)。

---

5. StringBuilder的容量预估

问题：StringBuilder默认容量为16，频繁扩容影响性能。

优化方案：预估容量，减少扩容次数。

// 预估容量
StringBuilder sb = new StringBuilder(n * 10);  // 假设每个元素平均10个字符

效果：减少扩容次数，提高性能。

---

6. 字符串比较的短路优化

问题：比较两个字符串时，逐个字符比较效率低。

优化方案：先比较长度，再比较内容。

// 优化：先比较长度
if (s1.length() != s2.length()) {
    return false;
}

// 再比较内容
return s1.equals(s2);

效果：长度不同时直接返回，避免逐个字符比较。

---

7. Trie树的懒删除

问题：删除节点时需要递归检查，效率低。

优化方案：使用懒删除，只标记isEnd为false，不实际删除节点。

public void delete(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            return;  // 单词不存在
        }
        node = node.children[index];
    }
    node.isEnd = false;  // 懒删除，只标记为非单词结尾
}

效果：删除操作的时间复杂度从O(m)降低到O(m)，但不需要递归检查。

---

8. 字符串哈希的模数选择

问题：模数选择不当可能导致冲突概率增加。

优化方案：选择大质数作为模数。

// 常用模数
private static final long MOD = 1000000007;  // 10^9+7
private static final long MOD = 1000000009;  // 10^9+9
private static final long MOD = 998244353;   // 998244353（NTT友好）

效果：大质数可以降低冲突概率。

---

练习题推荐

基础题（青铜-白银）

字符串基础操作：

1. LeetCode 344 - 反转字符串（Easy）
2. LeetCode 125 - 验证回文串（Easy）
3. LeetCode 242 - 有效的字母异位词（Easy）
4. LeetCode 387 - 字符串中的第一个唯一字符（Easy）
5. 码蹄集 MT1234 - 字符串反转（青铜）
6. 码蹄集 MT1345 - 回文判断（白银）

KMP算法入门：
7. LeetCode 28 - 找出字符串中第一个匹配项的下标（Easy）
8. LeetCode 459 - 重复的子字符串（Easy）
9. 码蹄集 MT1456 - 字符串匹配（白银）

---

中级题（黄金-钻石）

KMP算法进阶：
10. LeetCode 214 - 最短回文串（Hard）
11. LeetCode 686 - 重复叠加字符串匹配（Medium）
12. 码蹄集 MT1678 - 字符串匹配进阶（黄金）

字符串哈希：
13. LeetCode 187 - 重复的DNA序列（Medium）
14. LeetCode 1044 - 最长重复子串（Hard）
15. LeetCode 718 - 最长重复子数组（Medium）
16. 码蹄集 MT1789 - 子串比较（钻石）
17. 码蹄集 MT1890 - 最长重复子串（钻石）

Trie树：
18. LeetCode 208 - 实现Trie（前缀树）（Medium）
19. LeetCode 211 - 添加与搜索单词（Medium）
20. LeetCode 212 - 单词搜索II（Hard）
21. LeetCode 720 - 词典中最长的单词（Medium）
22. 码蹄集 MT1901 - 字典树实现（黄金）
23. 码蹄集 MT2012 - 字典树应用（钻石）

---

高级题（星耀-王者）

综合应用：
24. LeetCode 336 - 回文对（Hard）
25. LeetCode 1316 - 不同的循环子字符串（Hard）
26. LeetCode 1392 - 最长快乐前缀（Hard）
27. 码蹄集 MT2123 - 单词迷宫（星耀）
28. 码蹄集 MT2234 - 字符串综合（王者）

竞赛真题：
29. 码蹄集 MC0456 - 字符串匹配（2023省赛T6）
30. 码蹄集 MC0478 - 前缀树应用（2023国赛T8）

---

刷题建议

第1周：字符串基础操作

• 每天2-3题，掌握StringBuilder、双指针、回文判断
• 重点：LeetCode 344、125、242

第2周：KMP算法

• 每天1-2题，理解next数组的构建和匹配过程
• 重点：LeetCode 28、459、214

第3周：字符串哈希

• 每天1-2题，掌握前缀哈希和滚动哈希
• 重点：LeetCode 187、1044、718

第4周：Trie树

• 每天1-2题，掌握Trie树的构建和应用
• 重点：LeetCode 208、211、212

考前冲刺：

• 复习核心模板：KMP、字符串哈希、Trie树
• 做2-3道码蹄集真题：MC0456、MC0478
• 总结易错点和优化技巧

---

总结

字符串算法虽然在码蹄杯中占比不高（约5%），但一旦出现就是拉开差距的关键题。掌握字符串算法，你就能在关键时刻多拿一题，提升排名。

核心要点：

1. 字符串基础操作：使用StringBuilder拼接，双指针处理回文
2. KMP算法：O(n+m)时间复杂度的字符串匹配
3. 字符串哈希：O(1)时间复杂度的子串比较
4. Trie树：高效的前缀匹配和字符串存储

学习建议：

• 先掌握字符串基础操作，再学习KMP、字符串哈希、Trie树
• 理解算法原理，不要死记硬背模板
• 多做练习题，熟悉各种变体
• 总结易错点，避免在考场上犯错

竞赛策略：

• 字符串题通常出现在T6-T8，难度中等偏上
• 如果不熟悉KMP或Trie树，可以先跳过，做其他题
• 字符串哈希相对简单，优先掌握
• 考前复习核心模板，确保能快速写出

时间分配：

• 字符串基础操作：5-10分钟
• KMP算法：15-20分钟
• 字符串哈希：10-15分钟
• Trie树：15-20分钟

祝你在码蹄杯中取得好成绩！🎉