### 蓝桥杯 Python 字符串处理：哈希、KMP 和 Manacher 算法 #### 一、字符串哈希算法 字符串哈希是一种高效的字符串匹配方法，通过将字符串映射成唯一的数值来快速比较两个字符串是否相等。其核心思想是利用多项式滚动哈希函数计算字符串的哈希值。 对于子矩阵 `(a, b) * (x, y)` 的哈希值计算问题，可以通过二维前缀和的方式优化时间复杂度。具体来说，可以先预处理整个矩阵的哈希表，再通过差分运算得到任意子矩阵的哈希值[^1]。 以下是基于字符串哈希的实现代码： ```python MOD = 10**9 + 7 BASE = 31 def compute_hash(s): n = len(s) hash_values = [0] * (n + 1) powers = [1] * (n + 1) for i in range(1, n + 1): hash_values[i] = (hash_values[i - 1] * BASE + ord(s[i - 1])) % MOD powers[i] = (powers[i - 1] * BASE) % MOD return hash_values, powers def get_substring_hash(hash_values, powers, l, r): return (hash_values[r + 1] - hash_values[l] * powers[r - l + 1]) % MOD ``` --- #### 二、KMP 算法 KMP（Knuth-Morris-Pratt）算法用于高效模式匹配，能够在 O(n+m) 时间内完成字符串查找操作。它通过构建部分匹配表（Prefix Function），记录模式串中前后缀的最大公共长度，从而避免重复匹配。 以下是 KMP 算法的核心代码： ```python def build_lps(pattern): m = len(pattern) lps = [0] * m length = 0 i = 1 while i < m: 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 def kmp_search(text, pattern): n, m = len(text), len(pattern) lps = build_lps(pattern) i = j = 0 result = [] while i < n: if text[i] == pattern[j]: i += 1 j += 1 if j == m: result.append(i - j) j = lps[j - 1] elif i < n and text[i] != pattern[j]: if j != 0: j = lps[j - 1] else: i += 1 return result ``` --- #### 三、Manacher 算法 Manacher 算法专门用来寻找最长回文子串，可以在 O(n) 时间内解决问题。它的关键是通过对原字符串进行特殊转换（如 `#` 插入字符间），使得所有可能的回文中心都统一为单个字符形式。 以下是 Manacher 算法的具体实现： ```python def manacher(s): t = '#'.join('^{}$'.format(s)) n = len(t) p = [0] * n c = r = 0 max_len = center_index = 0 for i in range(1, n - 1): mirror = 2 * c - i if r > i: p[i] = min(r - i, p[mirror]) else: p[i] = 0 a, b = i + (p[i] + 1), i - (p[i] + 1) while t[a] == t[b]: p[i] += 1 a += 1 b -= 1 if i + p[i] > r: c = i r = i + p[i] if p[i] > max_len: max_len = p[i] center_index = i start = (center_index - max_len) // 2 return s[start:start + max_len] print(manacher("babad")) # 输出："bab" ``` --- #### 四、解题思路总结 针对蓝桥杯中的字符串处理题目，通常可以从以下几个方面入手： 1. **字符串哈希**适用于需要频繁查询子串或判断两段字符串是否相同的情况。 2. **KMP 算法**适合于大规模文本中查找特定模式串的任务。 3. **Manacher 算法**则专注于解决回文相关的问题，尤其是涉及动态更新最大回文子串时非常有效。 以上三种算法各有特点，可以根据实际需求灵活选用。 ---