2025-09-27：子字符串连接后的最长回文串Ⅰ 用go语言，给定两个

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

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

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

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

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

输出： 2。

解释：

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

题目来自力扣3503，3504。

回文串 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|

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

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

目的：

• 用 # 分隔，避免跨边界匹配。

• 反转 s 是为了方便后面找 x 与 y 的反转的公共前缀。

1. 对 ts 构建后缀数组 sa 和名次数组 rank。

2. 计算高度数组 height（相邻后缀的最长公共前缀 LCP）。

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 的某个后缀的最长公共前缀长度。

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

此时 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] 的两倍（因为延伸部分在回文两侧对称出现）。

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

• 后缀数组构建（Go 的 suffixarray.New）一般是 O(n log n) 或 O(n)（DC3/SA-IS），这里 n = len(s) + len(t) + 1，最大约 61。

• LCP 数组计算：O(n)。

• Manacher 算法：O(n)。

• 总体：O(n log n) 或 O(n)，由于 n ≤ 61，可视为常数。

• 后缀数组、rank、height、mx 等均为 O(n) 空间。

• Manacher 的 halfLen 数组也是 O(n)。

• 总空间 O(n)。

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

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

package mAInimport ( "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 0; i-- { // 反着再来一遍 ifint(sa[i]) |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 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)}

# -*-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 = 0 and idx = 0 and idx |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: 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 list: """构建后缀数组""" n = len(s) # 初始排名为字符的ASCII值 rk = [ord(c) for c in s] sa = list(range(n)) k = 1 while k 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