字符串转回文代码优化求助：前缀添加实现最少操作超时问题

原代码的问题在于每次循环都要截取子串并反转比较，时间复杂度为O(n²)，对于长度1e5的字符串，这种操作会直接导致超时——毕竟每轮比较都要花费O(i)的时间，累计下来就是平方级的运算量。

优化思路：用KMP前缀函数找最长前缀回文 #

我们需要找到原字符串中最长的前缀回文，这样只需在开头补全剩余部分的反转即可得到最短回文。利用KMP算法的前缀函数，可以在O(n)时间内高效找到这个最长前缀回文的长度：

1. 反转原字符串得到reversed_s
2. 构造拼接字符串t = s + '#' + reversed_s（加#是为了避免原串与反转串的无意义重叠匹配）
3. 计算t的前缀函数数组，数组最后一个值就是最长前缀回文的长度
4. 用reversed_s的前len(s)-max_len个字符（即需要补的部分）拼接原字符串，得到结果

优化后的代码 #

def compute_prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]
        while j > 0 and s[i] != s[j]:
            j = pi[j-1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

def make_palindrome(s):
    reversed_s = s[::-1]
    # 构造带分隔符的拼接串，避免跨串匹配
    t = s + '#' + reversed_s
    pi = compute_prefix_function(t)
    max_prefix_palindrome_len = pi[-1]
    # 取反转串的前(len(s)-max_len)个字符拼接原串
    return reversed_s[:len(s)-max_prefix_palindrome_len] + s

验证示例 #

• 输入abcd：最长前缀回文是a，补dcb得到dcbabcd
• 输入aabc：最长前缀回文是aa，补cb得到cbaabc
• 输入kayak：本身是回文，最长前缀回文长度等于串长，直接返回原串

这个方案的时间复杂度是O(n)，所有操作都是线性遍历，完全适配1e5长度的字符串，不会出现超时问题。

内容的提问来源于stack exchange，提问作者Hrant Baloyan