2025-09-27：子字符串连接后的最长回文串Ⅰ。用go语言，给定两个字符串 s 和 t。你可以从 s 中截取一段连续字符（也

福大大架构师每日一题

发布于 2025-12-18 13:15:35

350

2025-09-27：子字符串连接后的最长回文串Ⅰ。用go语言，给定两个字符串 s 和 t。你可以从 s 中截取一段连续字符（也可以不取，即空串），再从 t 中截取一段连续字符（同样可以为空），然后把 s 的那段放在前面、t 的那段接在后面，拼成一个新字符串。求通过这种拼接方式能得到的最长回文串的长度。

说明：回文串是正读和反读相同的字符串；子串指原字符串中连续的一段字符。

1 <= s.length, t.length <= 30。

s 和 t 仅由小写英文字母组成。

输入： s = "a", t = "a"。

输出： 2。

解释：

从 s 中选择 "a"，从 t 中选择 "a"，拼接得到 "aa"，这是一个长度为 2 的回文串。

题目来自力扣3503，3504。

1. 总体思路

回文串 x + y 有两种情况：

• 情况 A：|x| = |y| 此时回文要求 x 与 y 的反转相同。
• 情况 B：|x| > |y| 此时 x 可以写成 x = a + c + reverse(a)，其中 c 是回文中心（可能为空），y = reverse(b) 且 b 是 a 的前缀。
• 情况 C：|x| < |y| 对称地，y 可以写成 y = a + c + reverse(a)，x = reverse(b) 且 b 是 a 的前缀。

但代码里用对称性简化：计算 calc(s, t) 处理 |x| >= |y| 的情况，再计算 calc(reverse(t), reverse(s)) 处理 |x| < |y| 的情况，取最大值。

2. `calc(s, t)` 函数详解

2.1 构造字符串 `ts`

ts = t + "#" + reverse(s)

例如 t = "ab", s = "cd" → ts = "ab#dc"。

目的：

• 用 # 分隔，避免跨边界匹配。
• 反转 s 是为了方便后面找 x 与 y 的反转的公共前缀。

2.2 后缀数组与 LCP 数组

1. 对 ts 构建后缀数组 sa 和名次数组 rank。
2. 计算高度数组 height（相邻后缀的最长公共前缀 LCP）。

2.3 计算 `mx` 数组

mx[i] 的定义（关键）：在 reverse(s) 中，从位置 i 开始的子串，与 t 的某个后缀的 最长公共前缀长度。

计算方式：

• 正序遍历后缀数组，当遇到 t 中的后缀时，重置 lcp 为一个很大的值（表示可以开始记录 LCP）。
• 当遇到 reverse(s) 中的后缀时，更新 lcp = min(lcp, height[i])，然后记录到 mx 对应位置。
• 再逆序遍历一遍，同样更新 mx（因为可能从另一个方向有更大的 LCP）。
• 最后把 mx 再反转回来，对应到原 s 的位置。

这样 mx[i] 表示：在原 s 中，从位置 i 开始的子串，与 t 的某个后缀的最长公共前缀长度。

2.4 情况 A：`|x| = |y|`

如果 x从s的i开始，长度为L，那么要求y是t中某个长度为L的子串，并且x等于y的反转。等价于：x与t的某个后缀的前缀匹配长度至少为L，并且L最大就是mx[i]。所以情况 A 的最大长度是2 * max(mx)。

2.5 情况 B：`|x| > |y|`

此时 x 中间有一个回文子串，两侧对称，y 是 x 一侧的前缀的反转。

用 Manacher 算法 在 s 中找所有回文子串：

• 将 s 插入分隔符构造为 ^#c1#c2#...#$ 的形式。
• 对每个位置 i（在扩展后的字符串中），计算回文半径 halfLen[i]。
• 回文中心在 i，半径 hl 表示回文长度（原串中长度为 hl-1）。
• 设原 s 中对应左端点为 l = (i - hl) / 2。
• 此时 x 可以取这个回文串，并往左延伸一部分（即 s 中 l 之前的部分），但左侧延伸的长度不能超过 mx[l]（因为 y 必须匹配 t 的某个后缀）。
• 所以总回文长度 = 回文子串长度 (hl-1) + 左侧延伸匹配 t 的部分长度 mx[l] 的两倍（因为延伸部分在回文两侧对称出现）。

2.6 对称情况

calc(reverse(t), reverse(s)) 处理 |y| > |x| 的情况，逻辑与上面对称。

3. 复杂度分析

3.1 时间复杂度

• 后缀数组构建（Go 的 suffixarray.New）一般是 O(n log n) 或 O(n)（DC3/SA-IS），这里 n = len(s) + len(t) + 1，最大约 61。
• LCP 数组计算：O(n)。
• 两遍扫描更新 mx：O(n)。
• Manacher 算法：O(n)。
• 总体：O(n log n) 或 O(n)，由于 n ≤ 61，可视为常数。

3.2 空间复杂度

• 后缀数组、rank、height、mx 等均为 O(n) 空间。
• Manacher 的 halfLen 数组也是 O(n)。
• 总空间 O(n)。

4. 总结

该解法结合了后缀数组（用于计算两个字符串子串的反转匹配）和 Manacher 算法（用于快速枚举所有回文中心），通过对称处理两种情况，得到最长回文拼接串。

总时间复杂度：O(n log n) 或 O(n)（取决于后缀数组实现） 总空间复杂度：O(n) 其中 n = |s| + |t| + 1。

Go完整代码如下：

package main

import (
    "fmt"
    "index/suffixarray"
    "math"
    "slices"
    "unsafe"
)

func calc(s, t string)int {
    // ts = t + "#" + s
    ts := append([]byte(t), '#')
    tmp := []byte(s)
    slices.Reverse(tmp)
    ts = append(ts, tmp...)
    sa := (*struct {
        _  []byte
        sa []int32
    })(unsafe.Pointer(suffixarray.New(ts))).sa

    // 后缀名次数组 rank
    // 后缀 ts[i:] 位于后缀字典序中的第 rank[i] 个
    // 特别地，rank[0] 即 ts 在后缀字典序中的排名，rank[n-1] 即 ts[n-1:] 在字典序中的排名
    rank := make([]int, len(sa))
    for i, p := range sa {
        rank[p] = i
    }

    // 高度数组 height
    // sa 中相邻后缀的最长公共前缀 LCP
    // height[0] = height[len(sa)] = 0（哨兵）
    // height[i] = LCP(ts[sa[i]:], ts[sa[i-1]:])
    height := make([]int, len(sa)+1)
    h := 0
    for i, rk := range rank {
        if h > 0 {
            h--
        }
        if rk > 0 {
            for j := int(sa[rk-1]); i+h < len(ts) && j+h < len(ts) && ts[i+h] == ts[j+h]; h++ {
            }
        }
        height[rk] = h
    }

    mx := make([]int, len(s)+1)
    lcp := 0
    // sa[0] 对应 '#' 开头的后缀，不遍历
    for i := 1; i < len(sa); i++ {
        ifint(sa[i]) < len(t) {
            lcp = math.MaxInt // 找到了 t 中的后缀，可以开始计算 LCP
        } else {
            lcp = min(lcp, height[i])
            mx[int(sa[i])-len(t)-1] = lcp
        }
    }
    lcp = 0
    for i := len(sa) - 1; i > 0; i-- { // 反着再来一遍
        ifint(sa[i]) < len(t) {
            lcp = math.MaxInt
        } else {
            lcp = min(lcp, height[i+1])
            j := int(sa[i]) - len(t) - 1
            mx[j] = max(mx[j], lcp)
        }
    }
    slices.Reverse(mx)
    ans := slices.Max(mx) * 2// |x| = |y| 的情况

    // 计算 |x| > |y| 的情况
    s2 := append(make([]byte, 0, len(s)*2+3), '^')
    for _, c := range s {
        s2 = append(s2, '#', byte(c))
    }
    s2 = append(s2, '#', '$')
    halfLen := make([]int, len(s2)-2)
    halfLen[1] = 1
    boxM, boxR := 0, 0
    for i := 2; i < len(halfLen); i++ {
        hl := 1
        if i < boxR {
            hl = min(halfLen[boxM*2-i], boxR-i)
        }
        for s2[i-hl] == s2[i+hl] {
            hl++
            boxM, boxR = i, i+hl
        }
        halfLen[i] = hl

        if hl > 1 { // 回文子串不为空
            l := (i - hl) / 2// 回文子串左端点
            ans = max(ans, hl-1+mx[l]*2)
        }
    }
    return ans
}

func longestPalindrome(s, t string)int {
    return max(calc(s, t), calc(reverse(t), reverse(s)))
}

func reverse(s string)string {
    t := []byte(s)
    slices.Reverse(t)
    returnstring(t)
}

func main() {
    s := "a"
    t := "a"
    result := longestPalindrome(s, t)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def calc(s: str, t: str) -> int:
    # 构建新字符串: t + '#' + reverse(s)
    ts = t + '#' + s[::-1]
    n = len(ts)
    
    # 构建后缀数组和rank数组
    sa = build_suffix_array(ts)
    rank = [0] * n
    for i, pos in enumerate(sa):
        rank[pos] = i
    
    # 计算高度数组height
    height = [0] * (n + 1)
    h = 0
    for i, rk in enumerate(rank):
        if h > 0:
            h -= 1
        if rk > 0:
            j = sa[rk - 1]
            while i + h < n and j + h < n and ts[i + h] == ts[j + h]:
                h += 1
        height[rk] = h
    
    # 计算mx数组
    mx = [0] * (len(s) + 1)
    lcp = 0
    # 正向遍历
    for i in range(1, n):
        if sa[i] < len(t):
            lcp = float('inf')
        else:
            lcp = min(lcp, height[i])
            idx = sa[i] - len(t) - 1
            if idx >= 0 and idx < len(mx):
                mx[idx] = lcp
    
    lcp = 0
    # 反向遍历
    for i in range(n - 1, 0, -1):
        if sa[i] < len(t):
            lcp = float('inf')
        else:
            lcp = min(lcp, height[i + 1])
            idx = sa[i] - len(t) - 1
            if idx >= 0 and idx < len(mx):
                mx[idx] = max(mx[idx], lcp)
    
    mx = mx[::-1]
    ans = max(mx) * 2if mx else0  # |x| = |y|的情况
    
    # 使用Manacher算法处理|x| > |y|的情况
    # 构建新字符串用于Manacher算法: ^#a#b#c#$
    s2 = ['^']
    for c in s:
        s2.extend(['#', c])
    s2.extend(['#', '$'])
    
    half_len = [0] * len(s2)
    box_m, box_r = 0, 0
    
    for i in range(1, len(s2) - 1):
        hl = 1
        if i < box_r:
            hl = min(half_len[2 * box_m - i], box_r - i)
        
        while s2[i - hl] == s2[i + hl]:
            hl += 1
            if i + hl > box_r:
                box_m, box_r = i, i + hl
        
        half_len[i] = hl
        
        if hl > 1:  # 回文子串不为空
            l_index = (i - hl) // 2  # 回文子串左端点
            if l_index >= 0 and l_index < len(mx):
                ans = max(ans, hl - 1 + mx[l_index] * 2)
    
    return ans

def build_suffix_array(s: str) -> list:
    """构建后缀数组"""
    n = len(s)
    # 初始排名为字符的ASCII值
    rk = [ord(c) for c in s]
    sa = list(range(n))
    
    k = 1
    while k < n:
        # 根据第一关键字和第二关键字排序
        sa.sort(key=lambda i: (rk[i], rk[i + k] if i + k < n else-1))
        
        # 计算新的排名
        new_rk = [0] * n
        new_rk[sa[0]] = 0
        for i in range(1, n):
            prev, curr = sa[i - 1], sa[i]
            same = (rk[prev] == rk[curr] and 
                   (prev + k < n and curr + k < n and rk[prev + k] == rk[curr + k]))
            new_rk[curr] = new_rk[prev] + (0if same else1)
        
        rk = new_rk
        if rk[sa[-1]] == n - 1:
            break
        k <<= 1
    
    return sa

def longest_palindrome(s: str, t: str) -> int:
    """计算最长回文子串长度"""
    return max(calc(s, t), calc(t[::-1], s[::-1]))

def main():
    s = "a"
    t = "a"
    result = longest_palindrome(s, t)
    print(result)

if __name__ == "__main__":
    main()