字符串算法

1. 字符串基础

1.1 字符串的表示与编码

字符串是字符的有限序列，在算法中通常以数组形式存储。理解字符串的底层表示是掌握字符串算法的前提。

• ASCII 编码：7位编码，共128个字符，覆盖英文大小写、数字和常用符号
• Unicode 编码：统一编码标准，UTF-8为变长编码（1-4字节），UTF-16为2或4字节
• 字符串不可变性：在Python、Java中字符串不可变，修改需创建新对象

# Python中字符串的基本操作
s = "hello world"

# 字符串遍历
for ch in s:
    print(ch, end=' ')

# 字符串切片
print(s[0:5])   # "hello"
print(s[::-1])  # "dlrow olleh" 反转

# 字符与ASCII码互转
print(ord('A'))   # 65
print(chr(65))    # 'A'

1.2 字符串的常见操作复杂度

2. 字符串匹配算法

2.1 朴素匹配算法（Brute-Force）

逐字符比较，失配后模式串右移一位重新开始。

def brute_force_search(text, pattern):
    """朴素字符串匹配，返回所有匹配起始位置"""
    n, m = len(text), len(pattern)
    result = []
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            result.append(i)
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(brute_force_search(text, pattern))  # [10]

复杂度分析：

• 最好情况：O(n)，一次就匹配成功
• 最坏情况：O(m×n)，如 text=“AAAAA…A”, pattern=“AAAAB”

2.2 KMP 算法

KMP算法通过预处理模式串，构建部分匹配表（Next数组/LPS数组），避免主串指针回退。

Next 数组的构建

Next数组 next[i] 表示 pattern[0..i] 中最长相等前后缀的长度。

def build_next(pattern):
    """构建KMP的next数组（最长前缀后缀）"""
    m = len(pattern)
    next_arr = [0] * m
    j = 0  # 前缀末尾指针
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = next_arr[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        next_arr[i] = j
    return next_arr

def kmp_search(text, pattern):
    """KMP字符串匹配算法"""
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]

    next_arr = build_next(pattern)
    result = []
    j = 0  # 模式串指针

    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            result.append(i - m + 1)
            j = next_arr[j - 1]

    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern))  # [10]
print("Next数组:", build_next(pattern))  # [0, 0, 1, 2, 0, 1, 2, 3, 4]

KMP算法关键理解：

• 主串指针 i 永远不回退
• 失配时利用Next数组跳过已匹配的前缀部分
• 时间复杂度：O(m+n)，空间复杂度：O(m)

2.3 Rabin-Karp 算法

基于哈希的字符串匹配算法，将模式串和主串的子串映射为哈希值进行比较。

def rabin_karp_search(text, pattern):
    """Rabin-Karp字符串匹配算法"""
    n, m = len(text), len(pattern)
    if m > n:
        return []

    base = 256       # 字符集大小
    mod = 10**9 + 7  # 大质数取模

    # 计算base^(m-1) % mod
    h = 1
    for _ in range(m - 1):
        h = (h * base) % mod

    # 计算模式串和主串第一个窗口的哈希值
    pattern_hash = 0
    window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    result = []
    for i in range(n - m + 1):
        if pattern_hash == window_hash:
            # 哈希值相等时逐字符验证，避免哈希冲突
            if text[i:i + m] == pattern:
                result.append(i)
        if i < n - m:
            # 滚动哈希：移除最左字符，添加新字符
            window_hash = (window_hash - ord(text[i]) * h) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash = (window_hash + mod) % mod  # 确保非负

    return result

# 示例
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
print(rabin_karp_search(text, pattern))  # [0, 10]

Rabin-Karp 优势：

• 适合多模式匹配（多个模式串同时搜索）
• 滚动哈希使窗口滑动时O(1)更新哈希值
• 平均时间复杂度：O(n+m)，最坏O(n×m)（哈希冲突）

3. Trie 树（前缀树）

3.1 Trie 树的基本结构

Trie树是一种树形数据结构，用于高效存储和检索字符串集合。

class TrieNode:
    def __init__(self):
        self.children = {}    # 子节点映射
        self.is_end = False   # 是否为单词结尾
        self.count = 0        # 经过此节点的单词数

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """插入单词"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.count += 1
        node.is_end = True

    def search(self, word):
        """搜索单词是否存在"""
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        """检查是否存在以prefix为前缀的单词"""
        return self._find(prefix) is not None

    def _find(self, prefix):
        """查找前缀对应的节点"""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def count_prefix(self, prefix):
        """统计以prefix为前缀的单词数量"""
        node = self._find(prefix)
        return node.count if node else 0

# 示例
trie = Trie()
words = ["apple", "app", "application", "apply", "banana"]
for w in words:
    trie.insert(w)

print(trie.search("app"))          # True
print(trie.search("appl"))         # False
print(trie.starts_with("app"))     # True
print(trie.count_prefix("app"))    # 4

3.2 Trie 树的应用场景

• 自动补全：搜索引擎输入提示
• 拼写检查：快速判断单词是否在字典中
• IP路由：最长前缀匹配
• 词频统计：高效统计前缀出现次数

4. 字符串动态规划

4.1 最长公共子序列（LCS）

def longest_common_subsequence(text1, text2):
    """最长公共子序列"""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 回溯构造LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            lcs.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return dp[m][n], ''.join(reversed(lcs))

# 示例
s1 = "ABCBDAB"
s2 = "BDCABA"
length, lcs = longest_common_subsequence(s1, s2)
print(f"LCS长度: {length}, LCS: {lcs}")  # LCS长度: 4, LCS: BCBA

4.2 编辑距离（Levenshtein Distance）

def edit_distance(word1, word2):
    """编辑距离：最少操作次数使word1变为word2"""
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化边界
    for i in range(m + 1):
        dp[i][0] = i  # 删除
    for j in range(n + 1):
        dp[0][j] = j  # 插入

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )

    return dp[m][n]

# 示例
print(edit_distance("horse", "ros"))    # 3
print(edit_distance("intention", "execution"))  # 5

4.3 最长回文子串

def longest_palindrome(s):
    """最长回文子串 - 中心扩展法"""
    if not s:
        return ""

    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    result = ""
    for i in range(len(s)):
        # 奇数长度回文
        p1 = expand(i, i)
        if len(p1) > len(result):
            result = p1
        # 偶数长度回文
        p2 = expand(i, i + 1)
        if len(p2) > len(result):
            result = p2

    return result

# 示例
print(longest_palindrome("babad"))   # "bab" 或 "aba"
print(longest_palindrome("cbbd"))    # "bb"

5. 后缀数组

5.1 后缀数组的基本概念

后缀数组是将字符串的所有后缀按字典序排序后得到的数组，是处理字符串问题的强大工具。

def build_suffix_array(s):
    """构建后缀数组 - 倍增法"""
    n = len(s)
    # 初始按单个字符排序
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    k = 1

    while k < n:
        # 按第二关键字排序，再按第一关键字排序
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]]
            if (rank[sa[i]], rank[sa[i] + k] if sa[i] + k < n else -1) != \
               (rank[sa[i - 1]], rank[sa[i - 1] + k] if sa[i - 1] + k < n else -1):
                tmp[sa[i]] += 1
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2

    return sa

# 示例
s = "banana"
sa = build_suffix_array(s)
print("后缀数组:", sa)
for i in sa:
    print(f"  sa[{i}] = {s[i:]}")

6. 常见问题与解决方案

6.1 字符串匹配选择策略

6.2 常见陷阱

1. KMP中Next数组理解错误：Next数组存储的是最长相等前后缀长度，不是失配后应跳转的位置
2. Rabin-Karp哈希冲突：必须逐字符验证匹配结果
3. 编辑距离初始化遗漏：边界条件 dp[i][0]=i, dp[0][j]=j 容易忘记
4. 回文子串忽略偶数长度：中心扩展法需要同时考虑奇数和偶数长度

6.3 性能优化技巧

• 字符串匹配预处理模式串，减少主串扫描次数
• 大规模字符串使用滚动哈希避免重复计算
• Trie树可压缩为基数树（Radix Tree）减少空间
• 后缀数组构建可用SA-IS算法达到O(n)时间

7. 总结与最佳实践

7.1 核心要点

• KMP算法是字符串匹配的基石，理解Next数组的构建是关键
• Trie树是前缀问题的最优解，空间换时间的典型策略
• 字符串DP（LCS、编辑距离）是面试高频考点
• 后缀数组是高级字符串问题的通用工具

7.2 学习建议

1. 先掌握朴素匹配，再理解KMP的优化思路
2. 手动模拟Next数组的构建过程
3. 字符串DP问题注意状态定义和转移方程
4. 多练习LeetCode字符串专题（题号：3, 5, 28, 72, 139, 208, 214, 395）