如何优化Python双字符串拼接最长回文串生成函数？

原代码的核心问题是暴力枚举所有子串组合，时间复杂度达到O(n²m²(n+m))，对于长度超过20的字符串会变得极慢。以下是针对性的优化思路和实现：

核心优化方向 #

1. 过滤无效候选，减少判断次数 #

拼接串x+y是回文的必要条件是x的最后一个字符等于y的第一个字符（回文首尾字符必须一致）。基于此可以直接过滤掉大部分不可能的组合，避免无意义的拼接和判断。

2. 优先处理长串，提前终止流程 #

我们需要的是最长回文，因此按拼接串长度从大到小遍历：

• 一旦找到当前最长长度的合法回文，直接在该长度的候选中选字典序最小的返回，无需处理更短的串。
• 长度越大的组合数量越少（比如长度为len(a)+len(b)的组合只有1种：a+b），能大幅减少计算量。

3. 避免拼接字符串，直接判断回文 #

不用生成完整的x+y字符串，而是直接在x和y的原字符串上首尾对比，中途发现不匹配就提前终止判断，节省内存和时间。

优化后代码实现 #

def is_palindrome_concat(x, y):
    """直接在x、y上判断拼接后是否为回文，无需生成完整字符串"""
    len_x = len(x)
    len_y = len(y)
    total_len = len_x + len_y
    left, right = 0, total_len - 1
    
    while left < right:
        # 获取左指针对应的字符
        c_left = x[left] if left < len_x else y[left - len_x]
        # 获取右指针对应的字符
        c_right = x[right] if right < len_x else y[right - len_x]
        
        if c_left != c_right:
            return False
        left += 1
        right -= 1
    return True

def get_substrings_grouped(word):
    """生成所有子串，按长度分组（长度降序，同长度按字典序升序）"""
    len_to_subs = {}
    n = len(word)
    
    for length in range(1, n + 1):
        subs = []
        for start in range(n - length + 1):
            substr = word[start:start+length]
            subs.append(substr)
        # 同长度子串按字典序升序排序
        subs.sort()
        len_to_subs[length] = subs
    
    return len_to_subs

def buildPalindrome(a, b):
    # 按长度分组存储a、b的子串
    subs_a = get_substrings_grouped(a)
    subs_b = get_substrings_grouped(b)
    
    max_possible_len = len(a) + len(b)
    # 从最长可能长度开始遍历
    for total_len in range(max_possible_len, 1, -1):
        # 遍历a子串的所有可能长度l，对应b子串长度为total_len - l
        for l in range(1, len(a) + 1):
            b_l = total_len - l
            if b_l < 1 or b_l > len(b):
                continue
            if l not in subs_a or b_l not in subs_b:
                continue
            
            # 过滤首尾字符匹配的子串
            valid_a = [s for s in subs_a[l] if s[-1] == subs_b[b_l][0][0]]
            valid_b = [t for t in subs_b[b_l] if t[0] == valid_a[0][-1]] if valid_a else []
            if not valid_a or not valid_b:
                continue
            
            # 收集所有合法回文，返回字典序最小的
            candidates = []
            for s in valid_a:
                for t in valid_b:
                    if is_palindrome_concat(s, t):
                        candidates.append(s + t)
            if candidates:
                return min(candidates)
    
    # 无合法结果
    return "-1"

# 测试用例
print(buildPalindrome("bac", "bac"))   # 输出 aba
print(buildPalindrome("abc", "def"))   # 输出 -1
print(buildPalindrome("jdfh", "fds"))   # 输出 dfhfd

进阶优化：KMP算法快速匹配最长候选 #

对于更大的字符串（长度>50），可以用KMP算法的前缀函数快速找到最长匹配的后缀/前缀，避免枚举所有子串：

1. 构造字符串reverse(b) + '#' + a，计算前缀函数，找到a的后缀与reverse(b)的前缀的最长匹配长度k，候选串为a + b[:len(b)-k]。
2. 构造字符串reverse(a) + '#' + b，同理找到b的前缀与reverse(a)的后缀的最长匹配长度k，候选串为a[len(a)-k:] + b。
3. 验证这两个候选串是否为回文，取最长的（字典序最小的）返回。

这种方法的时间复杂度可以降到O(n+m)，适合处理大规模字符串。

内容的提问来源于stack exchange，提问作者Duck Dodgers