字符串处理面试攻略：哈希与KMP算法解析

在算法面试中，字符串处理是高频考点，其中字符串哈希和KMP算法因其高效性和实用性，常成为区分候选人能力的关键题目。本文将从原理、实现到应用场景，系统梳理这两类算法的核心要点，并提供可复用的解题模板。

一、字符串哈希：高效去重与模式匹配

1.1 哈希函数设计原理

字符串哈希的核心是将字符串映射为唯一数值，通过预处理实现快速比较。经典哈希函数设计需满足：

• 一致性：相同字符串必得相同哈希值
• 高效性：单次计算时间复杂度O(n)
• 抗碰撞性：不同字符串碰撞概率低

推荐使用多项式滚动哈希：

def string_hash(s: str, base=26, mod=1e9+7) -> int:
    hash_val = 0
    for ch in s:
        hash_val = (hash_val * base + ord(ch)) % mod
    return hash_val

参数选择建议：

• base取质数（如26/911/1e9+7）
• mod取大质数避免溢出
• 双哈希法（不同base+mod组合）可进一步降低碰撞

1.2 面试高频应用场景

场景1：字符串去重

def deduplicate(strings: List[str]) -> List[str]:
    hash_set = set()
    result = []
    for s in strings:
        h = string_hash(s)
        if h not in hash_set:
            hash_set.add(h)
            result.append(s)
    return result

场景2：快速字符串比较
比较两个长字符串时，先计算哈希值可快速排除不等情况，仅对哈希值相同的字符串进行逐字符比较。

场景3：Rabin-Karp算法基础
通过滑动窗口计算子串哈希，实现模式匹配：

def rabin_karp(text: str, pattern: str) -> List[int]:
    n, m = len(text), len(pattern)
    if m > n: return []
    base, mod = 26, 1e9+7
    pattern_hash = string_hash(pattern, base, mod)
    window_hash = string_hash(text[:m], base, mod)
    result = []
    power = base ** (m-1) % mod  # 预计算最高位权重
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i+m] == pattern:  # 双重验证防碰撞
                result.append(i)
        if i < n - m:
            # 滑动窗口更新哈希：减去最高位，乘以base，加上新字符
            window_hash = (window_hash - ord(text[i]) * power) % mod
            window_hash = (window_hash * base + ord(text[i+m])) % mod
    return result

二、KMP算法：线性时间模式匹配

2.1 前缀函数构建

KMP算法的核心是预处理模式串，构建部分匹配表（Partial Match Table）：

def build_lps(pattern: str) -> List[int]:
    lps = [0] * len(pattern)
    length = 0  # 当前最长前缀后缀长度
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length-1]  # 回退到前一个匹配位置
            else:
                lps[i] = 0
                i += 1
    return lps

关键点：

• 时间复杂度O(m)，m为模式串长度
• lps[i]表示pattern[0..i]的最长相等前后缀长度

2.2 完整匹配实现

def kmp_search(text: str, pattern: str) -> List[int]:
    n, m = len(text), len(pattern)
    if m == 0: return []
    lps = build_lps(pattern)
    i = j = 0  # text和pattern的当前比较位置
    result = []
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
            if j == m:
                result.append(i - j)
                j = lps[j-1]  # 继续寻找下一个匹配
        else:
            if j != 0:
                j = lps[j-1]  # 利用已匹配部分跳转
            else:
                i += 1
    return result

2.3 性能对比与优化

算法	预处理时间	匹配时间	总时间	空间复杂度
暴力匹配	O(1)	O(n*m)	O(n*m)	O(1)
Rabin-Karp	O(m)	O(n)	O(n+m)	O(1)
KMP	O(m)	O(n)	O(n+m)	O(m)

优化建议：

1. 对于短模式串（m<10），暴力匹配可能更快
2. 大字符集场景下，KMP比Rabin-Karp更稳定
3. 空间受限时，可优化LPS数组存储（如只保存关键点）

三、面试实战技巧

3.1 常见变种问题

问题1：统计所有出现位置

• 直接使用KMP或Rabin-Karp的返回结果即可

问题2：计算最长重复子串

• 构建后缀自动机或使用二分+哈希

问题3：通配符匹配

• 动态规划解法（O(n*m)）
• 改进KMP处理*和?（需修改状态转移）

3.2 代码实现注意事项

1. 边界条件处理：

   • 空字符串输入
   • 模式串比文本长
   • 完全匹配和部分匹配

2. 哈希冲突处理：

   • 双重哈希验证
   • 自然溢出处理（Python自动处理大数）

3. 性能优化：

   • 预计算幂次（如Rabin-Karp中的power）
   • 避免重复计算（如缓存子串哈希）

3.3 百度技术实践启示

在百度智能云的大数据处理场景中，字符串匹配算法有特殊优化需求：

1. 分布式处理：将文本分片后并行处理，需设计无状态哈希函数
2. 实时流处理：采用增量式KMP变种，支持动态文本更新
3. 多模匹配：结合AC自动机处理多关键词同时匹配

四、总结与学习建议

1. 基础巩固：

   • 手动推导KMP的LPS数组构建过程
   • 实现不同base的字符串哈希并测试碰撞率

2. 进阶方向：

   • 研究后缀数组、后缀自动机等高级字符串算法
   • 了解布隆过滤器在海量字符串去重中的应用

3. 面试准备：

   • 掌握两种算法的时空复杂度分析
   • 准备”为什么选择KMP而不是暴力匹配”等常见问题应答
   • 练习在白板上手写核心代码（注意变量命名和缩进）

通过系统掌握字符串哈希和KMP算法，开发者不仅能高效解决面试中的字符串匹配问题，更能为处理实际工程中的日志分析、文本搜索等场景打下坚实基础。建议结合LeetCode字符串专题（如28.实现strStr()、459.重复的子字符串）进行针对性练习。