解题思路

我们需要找到最长的扭动回文串，它可以是：

1. 纯 $A$ 中的回文子串；
2. 纯 $B$ 中的回文子串；
3. 由 $A$ 和 $B$ 拼接而成的回文串 $S(i,j,k)$，其中：
   • $A[i..j]$ 与 $B[j..k]$ 拼接后是回文串；
   • 注意 $A$ 和 $B$ 在位置 $j$ 处重叠（$A_j$ 和 $B_j$ 是同一个下标的不同字符串的字符）。

关键点

对于情况 3，扭动回文串 $S(i,j,k)$ 的形式是：

A[i] ... A[j]  B[j] ... B[k]

并且整个字符串是回文的。

由于回文串对称，我们可以枚举中心点，然后向两边扩展。
但这里中心点可能落在 $A$ 或 $B$ 中，也可能落在 $A$ 和 $B$ 的拼接处。

方法

1. 预处理
   使用 Manacher 算法分别求出 $A$ 和 $B$ 中每个位置作为中心时的最长回文半径（包括奇偶长度统一处理）。

2. 枚举分割点
   对于情况 3，我们枚举 $j$（$1 \leq j \leq N$），表示 $A$ 的子串以 $j$ 结尾，$B$ 的子串以 $j$ 开头。
   我们要求：

   • $A[i..j]$ 与 $B[j..k]$ 拼接后是回文串；
   • 并且 $A[i..j]$ 是 $A$ 的一个回文后缀，$B[j..k]$ 是 $B$ 的一个回文前缀。

   可以这样考虑：

   • 固定 $j$，让 $A$ 中 $j$ 往左的回文半径和 $B$ 中 $j$ 往右的回文半径尽可能长，然后尝试拼接。
   • 但拼接后可能还可以继续向 $A$ 的左边和 $B$ 的右边扩展（因为 $A$ 的左部分和 $B$ 的右部分可以继续匹配）。

3. 二分 + 哈希
   可以用二分法检查在 $j$ 处，$A$ 往左和 $B$ 往右能匹配多长（即 $A$ 的某个后缀与 $B$ 的某个前缀的逆序匹配）。
   这样，对于每个 $j$，我们可以得到最长的扭动回文串长度。

4. 合并答案
   取三种情况的最大值。

算法复杂度

• Manacher：$O(N)$
• 二分 + 哈希：$O(N \log N)$
• 总体：$O(N \log N)$。

说明

• Manacher 用于快速求出每个位置为中心的最长回文半径。
• 哈希 用于快速比较子串是否相等（正向与反向）。
• 二分 用于确定在位置 $j$ 处 $A$ 和 $B$ 能匹配的最大长度。
• 最终答案取三种情况的最大值。