题解

问题分析

题目要求找到字符串中最长的“双倍回文子串”，其核心约束有三：

1. 长度为 ( 4 ) 的倍数（设为 ( 4L )）；
2. 子串本身是回文（即 ( x = x^R )）；
3. 子串的前半部分（长度 ( 2L )）和后半部分（长度 ( 2L )）均为回文。

结合双倍回文的定义 ( x = ww^Rww^R )，可推导出关键性质：子串的中心必然是两个相邻字符（偶长度回文的中心），且以该中心为界，左右对称位置需满足回文嵌套关系。

关键思路

1. 用 Manacher 算法预处理回文信息：
   Manacher 算法能在 ( O(n) ) 时间内计算出每个位置为中心的最长回文半径，其中：

   • 奇数长度回文的中心用原字符串的字符位置表示；
   • 偶数长度回文的中心用两个字符之间的“虚拟位置”表示（如字符串 ( s[0..n-1] ) 的虚拟位置为 ( 1,3,...,2n-1 )）。
     预处理后，可通过数组 ( p ) 快速查询任意中心的最长回文半径，判断某段是否为回文。

2. 枚举双倍回文的中心与长度：
   双倍回文长度为 ( 4L )，其中心是长度 ( 2L ) 回文的中心（偶长度回文的虚拟位置）。枚举所有可能的虚拟中心 ( c )，并从大到小尝试可能的 ( L )（保证 ( 4L \leq 当前最长答案 ) 以剪枝），验证以下条件：

   • 以 ( c ) 为中心、长度 ( 2L ) 的子串是回文（满足双倍回文前半部分的回文要求）；
   • 以 ( c ) 为中心、长度 ( 4L ) 的子串是回文（满足双倍回文本身的回文要求）。
     若两个条件均满足，则 ( 4L ) 是候选最长长度。

代码实现

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    s = input[1] if len(input) > 1 else ''  # 处理输入可能的换行分割
    
    if n < 4:
        print(0)
        return
    
    # Step 1: Manacher算法预处理，构造转换字符串并计算p数组
    # 转换原字符串s为t，插入特殊字符#（如s=abc→t=#a#b#c#）
    t = ['#']
    for c in s:
        t.append(c)
        t.append('#')
    m = len(t)  # m = 2n + 1
    p = [0] * m  # p[i]表示以t[i]为中心的最长回文半径（包含t[i]）
    center = right = 0  # 当前最右回文的中心和右边界
    
    for i in range(m):
        # 计算i关于center的对称点
        mirror = 2 * center - i
        # 若i在right内，初始化p[i]为min(right-i, p[mirror])
        if i < right:
            p[i] = min(right - i, p[mirror])
        # 尝试扩展以i为中心的回文
        left = i - (p[i] + 1)
        right_ext = i + (p[i] + 1)
        while left >= 0 and right_ext < m and t[left] == t[right_ext]:
            p[i] += 1
            left -= 1
            right_ext += 1
        # 更新最右回文的中心和右边界
        if i + p[i] > right:
            center = i
            right = i + p[i]
    
    # Step 2: 枚举所有可能的双倍回文中心（偶长度回文的虚拟中心，对应t中的#位置）
    max_len = 0
    # 虚拟中心c在t中的位置：只能是#的位置（即原字符串中两个字符之间的位置）
    # t中#的位置为0,2,4,...,2n（共n+1个）
    for c in range(0, m, 2):
        # 双倍回文长度为4L，需满足4L <= 当前max_len（剪枝，从大到小试）
        # 最大可能的L：4L <= n → L <= n//4；同时中心c的回文半径需支持2L长度
        max_possible_L = min(n // 4, p[c] // 2)
        # 从最大可能的L开始尝试，找到即更新max_len并break
        for L in range(max_possible_L, 0, -1):
            current_4L = 4 * L
            if current_4L <= max_len:
                break  # 更小的L无法更新max_len，剪枝
            # 条件1：以c为中心，长度2L的子串是回文（p[c] >= 2L → 半径足够）
            if p[c] < 2 * L:
                continue
            # 条件2：以c为中心，长度4L的子串是回文（p[c] >= 4L → 半径足够）
            if p[c] >= 4 * L:
                max_len = current_4L
                break  # 当前L已最大，无需尝试更小L
    
    print(max_len)

if __name__ == "__main__":
    main()

复杂度分析

1. Manacher 算法预处理：时间复杂度 ( O(n) )，需处理长度为 ( 2n+1 ) 的转换字符串，线性遍历即可完成。
2. 枚举与验证：
   • 枚举虚拟中心：共 ( n+1 ) 个（原字符串中两个字符之间的位置）；
   • 每个中心尝试的 ( L ) 从大到小，且一旦找到满足条件的 ( L ) 就剪枝，实际平均尝试次数极少；
   • 验证条件仅需查询预处理的 ( p ) 数组（( O(1) ) 操作）。

整体时间复杂度为 ( O(n) )，可高效处理 ( n \leq 5 \times 10^5 ) 的大规模数据。