P4324 [JSOI2016] Twisted Palindrome String

JYY has two strings $A$ and $B$, both of length $N$. A "twisted string" $S(i,j,k)$ is formed by concatenating the substring of $A$ from the $i$-th character to the $j$-th character and the substring of $B$ from the $j$-th character to the $k$-th character. For example, if $A=\mathtt{XYZ}$ and $B=\mathtt{UVW}$, then the twisted string $S(1,2,3)=\mathtt{XYVW}$. JYY defines a "twisted palindrome" as one of the following: - A palindrome in $A$; - A palindrome in $B$; - Or a twisted string $S(i,j,k)$ that is a palindrome. Now JYY wants to find the longest twisted palindrome.

The first line contains a positive integer $N$. The second line contains a string $A$ of length $N$ consisting of uppercase letters. The third line contains a string $B$ of length $N$ consisting of uppercase letters.

Output a single integer on the first line, the length of the longest twisted palindrome.

Sample explanation: The twisted palindrome in the best solution is shown below (characters not in the palindrome are marked with `.`): ```pain .BC.. ..ECB ``` Constraints: For all testdata, $1 \leq N \leq 10^5$. Translated by ChatGPT 5