跳到主要内容

字符串算法

字符串算法是处理文本数据的核心技术，广泛应用于文本编辑器、搜索引擎、生物信息学等领域。本章将深入讲解字符串匹配、回文检测等经典算法，帮助你理解其原理并掌握实际应用。

字符串基础​

字符串的表示与操作​

在不同编程语言中，字符串的表示和操作方式有所不同：

// Java 字符串基本操作
String s = "Hello World";

// 基本属性
int len = s.length();           // 长度
char c = s.charAt(0);           // 访问字符: 'H'

// 常用操作
String sub = s.substring(0, 5); // 子串: "Hello"
int idx = s.indexOf("World");   // 查找: 6
boolean eq = s.equals("hello"); // 比较: false
String upper = s.toUpperCase(); // 转换: "HELLO WORLD"

// 分割与连接
String[] parts = "a,b,c".split(",");     // ["a", "b", "c"]
String joined = String.join("-", parts); // "a-b-c"

StringBuilder 的高效拼接​

在需要频繁拼接字符串时，使用 StringBuilder 比直接使用 + 操作符高效得多：

// 低效方式：每次拼接都创建新字符串对象
String result = "";
for (int i = 0; i < 1000; i++) {
    result += i;  // 时间复杂度 O(n²)
}

// 高效方式：StringBuilder
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000; i++) {
    sb.append(i);  // 时间复杂度 O(n)
}
String result = sb.toString();

原理：Java 中 String 是不可变对象，每次拼接都会创建新对象并复制内容。StringBuilder 内部使用可变字符数组，追加操作只需扩容（均摊 O(1)）。

字符串匹配算法​

字符串匹配问题：给定文本 TT（长度为 nn）和模式串 PP（长度为 mm），找出 PP 在 TT 中所有出现的位置。

暴力匹配算法​

最直观的方法是逐个位置尝试匹配：

/**
 * 暴力字符串匹配
 * 时间复杂度: O(n * m) 最坏情况
 * 空间复杂度: O(1)
 * 
 * @param text 文本串
 * @param pattern 模式串
 * @return 匹配的起始位置列表
 */
public List<Integer> bruteForceMatch(String text, String pattern) {
    List<Integer> positions = new ArrayList<>();
    int n = text.length();
    int m = pattern.length();
    
    // 枚举所有可能的起始位置
    for (int i = 0; i <= n - m; i++) {
        boolean match = true;
        for (int j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) {
                match = false;
                break;  // 失配，尝试下一个位置
            }
        }
        if (match) {
            positions.add(i);
        }
    }
    
    return positions;
}

问题：在某些情况下效率很低。例如，T=T = "AAAA...AB"，P=P = "AAAB"，每次失配都在最后一个字符，时间复杂度退化为 O(n⋅m)O(n \cdot m)。

KMP 算法​

KMP 算法（Knuth-Morris-Pratt）通过预处理模式串，利用已匹配信息跳过不必要的比较，将时间复杂度优化到 O(n+m)O(n + m)。

核心概念：前缀函数​

前缀函数 π[i]\pi[i] 定义为：子串 P[0..i]P[0..i] 的最长相等真前缀和真后缀的长度。

真前缀/真后缀：不等于整个字符串的前缀/后缀。

例如，对于模式串 "ABABC"：

ii子串 P[0..i]P[0..i]最长相等前后缀π[i]\pi[i]
0A无0
1AB无0
2ABAA1
3ABABAB2
4ABABC无0

前缀函数数组为 [0,0,1,2,0][0, 0, 1, 2, 0]。

前缀函数的计算​

利用已经计算出的 π\pi 值高效计算当前位置：

/**
 * 计算模式串的前缀函数
 * 时间复杂度: O(m)
 * 
 * @param pattern 模式串
 * @return 前缀函数数组
 */
public int[] computePrefixFunction(String pattern) {
    int m = pattern.length();
    int[] pi = new int[m];
    pi[0] = 0;  // 单个字符没有真前缀和真后缀
    
    int j = 0;  // 当前最长相等前后缀的长度
    
    for (int i = 1; i < m; i++) {
        // 当前字符不匹配时，回退到更短的相等前后缀
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = pi[j - 1];
        }
        
        // 如果匹配，扩展相等前后缀
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        
        pi[i] = j;
    }
    
    return pi;
}

KMP 匹配过程​

/**
 * KMP 字符串匹配算法
 * 时间复杂度: O(n + m)
 * 空间复杂度: O(m)
 * 
 * @param text 文本串
 * @param pattern 模式串
 * @return 所有匹配位置的列表
 */
public List<Integer> kmpSearch(String text, String pattern) {
    List<Integer> positions = new ArrayList<>();
    
    if (pattern.isEmpty()) {
        positions.add(0);
        return positions;
    }
    
    int n = text.length();
    int m = pattern.length();
    
    // 预处理：计算前缀函数
    int[] pi = computePrefixFunction(pattern);
    
    int j = 0;  // 模式串中已匹配的长度
    
    for (int i = 0; i < n; i++) {
        // 失配时根据前缀函数跳转
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = pi[j - 1];
        }
        
        // 匹配成功，推进
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        
        // 完全匹配
        if (j == m) {
            positions.add(i - m + 1);
            // 继续搜索下一个匹配
            j = pi[j - 1];
        }
    }
    
    return positions;
}

算法原理图解​

假设在文本 "ABABABABC" 中搜索模式 "ABABC"：

文本:   A B A B A B A B C
模式:   A B A B C
        ↑
        i=0, j=0, 匹配

文本:   A B A B A B A B C
模式:   A B A B C
            ↑
            i=4, j=4, 失配 (A ≠ C)
            根据前缀函数 pi[3]=2, j 回退到 2

文本:   A B A B A B A B C
模式:       A B A B C
                ↑
                从 j=2 继续匹配

关键点：当失配发生时，我们已经知道文本中有一部分与模式的前缀匹配。前缀函数告诉我们这个匹配部分的 "边界"，可以跳过已知的匹配内容。

Rabin-Karp 算法​

Rabin-Karp 算法使用哈希函数进行字符串匹配，特别适合多模式匹配问题。

核心思想​

将字符串转换为数值（哈希值），通过比较哈希值快速排除不可能匹配的位置。

滚动哈希：利用前一个位置的哈希值高效计算下一个位置的哈希值。

哈希函数设计​

使用多项式哈希：

H(s)=∑i=0m−1si⋅dm−1−i mod qH(s) = \sum_{i=0}^{m-1} s_i \cdot d^{m-1-i} \bmod q

其中 dd 是进制（通常取字符集大小或一个大质数），qq 是模数（大质数）。

滚动计算：

H(si+1..i+m)=d⋅(H(si..i+m−1)−si⋅dm−1)+si+m mod qH(s_{i+1..i+m}) = d \cdot (H(s_{i..i+m-1}) - s_i \cdot d^{m-1}) + s_{i+m} \bmod q

实现​

/**
 * Rabin-Karp 字符串匹配算法
 * 时间复杂度: 平均 O(n + m)，最坏 O(n * m)
 * 空间复杂度: O(1)
 */
public List<Integer> rabinKarpSearch(String text, String pattern) {
    List<Integer> positions = new ArrayList<>();
    
    int n = text.length();
    int m = pattern.length();
    
    if (m > n || m == 0) {
        return positions;
    }
    
    // 哈希参数
    final int BASE = 256;      // 进制（字符集大小）
    final int MOD = 101;       // 模数（实际应用中应取大质数）
    
    // 计算 BASE^(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) {
                positions.add(i);
            }
        }
        
        // 滚动计算下一个窗口的哈希值
        if (i < n - m) {
            textHash = (BASE * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % MOD;
            
            // 处理负数
            if (textHash < 0) {
                textHash += MOD;
            }
        }
    }
    
    return positions;
}

应用场景​

  • 多模式匹配：预处理所有模式的哈希，一次扫描完成
  • 二维模式匹配：将二维模式按行/列哈希
  • 文档相似度检测：比较文档块的哈希值

算法对比​

算法预处理时间匹配时间空间复杂度特点
暴力O(1)O(1)O(n⋅m)O(n \cdot m)O(1)O(1)简单直观
KMPO(m)O(m)O(n)O(n)O(m)O(m)稳定高效
Rabin-KarpO(m)O(m)平均 O(n)O(n)O(1)O(1)适合多模式

回文算法​

回文是正读和反读都相同的字符串，如 "level"、"racecar"。

中心扩展法​

从每个可能的中心向两边扩展，寻找最长回文：

/**
 * 中心扩展法寻找最长回文子串
 * 时间复杂度: O(n²)
 * 空间复杂度: O(1)
 */
public String longestPalindromeExpand(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    
    int start = 0, maxLength = 1;
    
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度回文（单中心）
        int len1 = expandAroundCenter(s, i, i);
        // 偶数长度回文（双中心）
        int len2 = expandAroundCenter(s, i, i + 1);
        
        int len = Math.max(len1, len2);
        
        if (len > maxLength) {
            maxLength = len;
            start = i - (len - 1) / 2;
        }
    }
    
    return s.substring(start, start + maxLength);
}

/**
 * 从中心向两边扩展，返回回文长度
 */
private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

Manacher 算法​

Manacher 算法在线性时间内找到最长回文子串，核心思想是利用已知的回文信息加速后续计算。

预处理：统一奇偶长度​

通过在字符间插入特殊字符（如 #），将所有回文转化为奇数长度：

原串:    a b b a
处理后: #a#b#b#a#

核心概念​

  • 回文半径 R[i]R[i]：以位置 ii 为中心的最长回文的半径（包含中心）
  • 当前最右边界 maxRightmaxRight：目前发现的回文能到达的最右位置
  • 对称中心 centercenter：到达 maxRightmaxRight 的回文的中心

算法原理​

利用回文的对称性：

  • 如果当前位置 ii 在某个已知回文内（i<maxRighti < maxRight），则 R[i]R[i] 至少等于其对称位置的半径
  • 然后尝试扩展，更新 maxRightmaxRight 和 centercenter
/**
 * Manacher 算法寻找最长回文子串
 * 时间复杂度: O(n)
 * 空间复杂度: O(n)
 */
public String longestPalindromeManacher(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    
    // 预处理：插入特殊字符
    StringBuilder sb = new StringBuilder("#");
    for (char c : s.toCharArray()) {
        sb.append(c).append("#");
    }
    String t = sb.toString();
    
    int n = t.length();
    int[] radius = new int[n];  // 回文半径数组
    
    int center = 0;    // 当前中心
    int maxRight = 0;  // 最右边界
    
    int maxRadius = 0;
    int maxCenter = 0;
    
    for (int i = 0; i < n; i++) {
        // 利用对称性快速初始化
        if (i < maxRight) {
            int mirror = 2 * center - i;  // 对称位置
            radius[i] = Math.min(maxRight - i, radius[mirror]);
        }
        
        // 尝试扩展
        int left = i - radius[i] - 1;
        int right = i + radius[i] + 1;
        while (left >= 0 && right < n && t.charAt(left) == t.charAt(right)) {
            radius[i]++;
            left--;
            right++;
        }
        
        // 更新最右边界和中心
        if (i + radius[i] > maxRight) {
            center = i;
            maxRight = i + radius[i];
        }
        
        // 记录最大值
        if (radius[i] > maxRadius) {
            maxRadius = radius[i];
            maxCenter = i;
        }
    }
    
    // 还原原始字符串中的位置
    int start = (maxCenter - maxRadius) / 2;
    return s.substring(start, start + maxRadius);
}

字符串哈希​

字符串哈希可以快速计算任意子串的哈希值，用于高效比较子串。

前缀哈希​

预先计算前缀哈希数组，然后利用前缀差计算任意子串哈希：

H(s[l..r])=H(s[0..r])−H(s[0..l−1])⋅dr−l+1H(s[l..r]) = H(s[0..r]) - H(s[0..l-1]) \cdot d^{r-l+1}

/**
 * 字符串哈希工具类
 */
public class StringHash {
    private long[] hash;     // 前缀哈希
    private long[] power;    // 进制的幂次
    private final long BASE = 31;
    private final long MOD = 1_000_000_007;
    
    public StringHash(String s) {
        int n = s.length();
        hash = new long[n + 1];
        power = new long[n + 1];
        
        power[0] = 1;
        for (int i = 0; i < n; i++) {
            hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % MOD;
            power[i + 1] = (power[i] * BASE) % MOD;
        }
    }
    
    /**
     * 获取子串 s[l..r] 的哈希值（0-indexed，闭区间）
     */
    public long getHash(int l, int r) {
        return (hash[r + 1] - hash[l] * power[r - l + 1] % MOD + MOD) % MOD;
    }
    
    /**
     * 比较两个子串是否相等
     */
    public boolean compare(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
}

应用场景​

  1. 快速判断子串相等：O(1)O(1) 时间
  2. 最长公共前缀：二分 + 哈希
  3. 字符串的不同子串数目：哈希去重

小结​

字符串算法的核心要点：

问题算法时间复杂度核心思想
字符串匹配KMPO(n+m)O(n + m)利用失配信息跳过比较
字符串匹配Rabin-Karp平均 O(n+m)O(n + m)滚动哈希快速比较
最长回文中心扩展O(n2)O(n²)从中心向两边扩展
最长回文ManacherO(n)O(n)利用对称性加速
子串哈希前缀哈希O(n)O(n) 预处理前缀差计算子串哈希

选择建议：

  • 单模式匹配：优先使用 KMP
  • 多模式匹配：考虑 Rabin-Karp 或 AC 自动机
  • 回文问题：Manacher 效率最高，中心扩展实现简单
  • 频繁子串比较：使用字符串哈希

练习​

基础：

  1. LeetCode 28：实现 strStr()（KMP 练习）
  2. LeetCode 5：最长回文子串（中心扩展 / Manacher）
  3. LeetCode 409：最长回文串（字符计数）
  4. LeetCode 647：回文子串（中心扩展）

进阶： 5. LeetCode 459：重复的子字符串（KMP 应用） 6. LeetCode 214：最短回文串（KMP 应用） 7. LeetCode 131：分割回文串（回溯 + 回文判断） 8. LeetCode 132：分割回文串 II（DP + 预处理）

挑战： 9. LeetCode 44：通配符匹配（动态规划） 10. LeetCode 10：正则表达式匹配（动态规划） 11. 实现 AC 自动机（多模式匹配） 12. 实现后缀数组（复杂字符串问题）