跳到主要内容

字符串算法

字符串算法主要涵盖了最常见的匹配算法、回文检测及其变体。

字符串基础操作​

  • 比较、拼接 (String vs StringBuilder)。
  • 前缀与后缀。
  • 哈希。

字符串匹配​

1. 暴力匹配 (Brute Force) - O(mn)​

2. KMP 算法 - O(m+n)​

KMP 算法的核心是 next 数组（或 prefix table），用于在不匹配时跳过已比较过的冗余部分。

  • 核心思想：利用已匹配的前缀后缀的最长相等公共长度。
public int kmp(String s, String p) {
    int n = s.length(), m = p.length();
    int[] next = getNext(p);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || s.charAt(i) == p.charAt(j)) {
            i++; j++;
        } else {
            j = next[j];
        }
    }
    return j == m ? i - m : -1;
}

private int[] getNext(String p) {
    int m = p.length();
    int[] next = new int[m];
    next[0] = -1;
    int k = -1, j = 0;
    while (j < m - 1) {
        if (k == -1 || p.charAt(j) == p.charAt(k)) {
            k++; j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

3. Z-Algorithm​

4. Rabin-Karp (哈希匹配)​

  • 核心思想：利用滚动哈希快速计算长度为 m 的子串哈希。

回文专题​

1. 验证回文 (双指针) - O(n)​

2. 最长回文子串 (Manacher 算法 / 动态规划)​

  • 暴力法 开销太大 O(n³)。
  • 中心扩散 O(n²)。
  • Manacher 可以做到 O(n)，核心是利用回文的对称性避免重复搜索。

练习​

  1. LeetCode 28：实现 strStr() (KMP 练习)
  2. LeetCode 459：重复的子字符串 (KMP 练习)
  3. LeetCode 5：最长回文子串
  4. LeetCode 131/132：分割回文串 (回溯 + DP/字符串)
  5. LeetCode 44/10：通配符/正则表达式匹配 (字符串 + DP)
  6. 实现 字符串滚动哈希 构建 Rabin-Karp 算法。
  7. 理解 字典树 (Trie) 及其在字符串集合搜索中的应用。