构建从两个字符串生成最长回文串的高效算法-Python教程-PHP中文网

构建从两个字符串生成最长回文串的高效算法

本文介绍一种时间复杂度显著优于暴力枚举的算法，通过中心扩展法结合字典树（trie）加速子串匹配，用于求解“由字符串 a 的非空子串与字符串 b 的非空子串拼接而成的最长回文串”，并在长度相同时返回字典序最小的结果。

本文介绍一种时间复杂度显著优于暴力枚举的算法，通过中心扩展法结合字典树（trie）加速子串匹配，用于求解“由字符串 a 的非空子串与字符串 b 的非空子串拼接而成的最长回文串”，并在长度相同时返回字典序最小的结果。

在解决 Build Palindrome from Two Strings 问题时，原始暴力方法的时间复杂度高达 O(n⁴)：它枚举所有 a 的子串（O(n²)）、所有 b 的子串（O(m²)），再两两拼接并验证回文（O(n+m)），总开销对中等规模输入（如长度 > 40）已不可接受。

高效解法的核心思想是回文中心驱动 + 字典树预处理，将复杂度降至近似 O((n+m)³) 最坏、实践中接近 O(n² + m²) 的水平。其关键洞察在于：

所有合法答案 p = x + y（其中 x ⊆ a, y ⊆ b, x,y ≠ ε）必为回文，因此其结构必然关于某个“中心”对称；
该中心可能完全落在 a 中（即 x 覆盖中心并向右延伸，y 补足左侧镜像部分），或完全落在 b 中（此时需交换角色，等价于在 b 中找中心、用 a 补镜像）；
因此我们只需遍历所有可能的中心位置（共 2n−1 个奇/偶中心），对每个中心快速计算：以该中心在 a 中能形成的最大回文核心，再尝试用 b 的子串“向左补全”缺失的前缀。

为此，我们预先为字符串 b 构建一个子串 Trie：每个节点代表一个字符，从根到某节点的路径即对应 b 的一个子串。这样，检查“某字符串是否为 b 的子串”可降为 O(L) 的 Trie 遍历（L 为字符串长度）。

以下是优化后的完整实现（含清晰注释与边界处理）：

def buildTrie(s):
    """构建字典树，存储 s 的所有非空子串"""
    trie = {}
    for i in range(len(s)):
        node = trie
        for j in range(i, len(s)):
            node = node.setdefault(s[j], {})
    return trie

def longest_palindrome_candidate(palin1, palin2):
    """返回更优候选：先比长度，再比字典序"""
    if len(palin1) > len(palin2):
        return palin1
    if len(palin1)  0 and right_idx <p>✅ <strong>关键优势说明</strong>：</p>