Divide two strings to form palindrome

Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

I've tried bruteforce, and this can be achieved in $O(n^2)$. I'm looking for any kind of optimization that is faster than $O(n^2)$. I'm not familiar with backtracking and DP. So, can anyone throw some light?

Some notations in Python convention

• $S[:i]$ means the first $i$ letter of string $S$.

• $S[-i:]$ means the last $i$ letter of string $S$. ($S[-0:]$ is the empty string, which is not Python convention.)

• $S+T$ means the concatenation of $S$ and $T$.

The problem in clearer terms

Given two strings, $A$ and $B$, of equal length $n$, find whether $A[:i]+ B[-(n-i):]$ is a palindrome for some $i$.

Brute force

For each $i$ in $0, 1, \cdots, n$, we can check if $A[:i]+ B[-(n-i):]$ is a palindrome. This search by brute force runs in $O(n^2)$. Its average time-complexity is $O(n)$ under some reasonable assumptions. It is very easy to implement.

Algorithm in $O(n)$

Let us take a closer look what happens when we get a palindrome. For example,
$$\begin{aligned}
A&=ab12321xy\\
B&=\text{}5\text{*}4ba\\
C=A[\text{:}7]+B[-2\text{:}]&=ab12321ba\quad \text{which is a palindrome.}
\end{aligned}$$

Note that 12321 in $C$ is a palindrome that sits in the middle of $C$, which is not surprising since the central part of a palindrome is also a palindrome. Since the lengths of $A$ and $B$ are the same, that 12321 should sit in the middle of $A$ as well.

Note the remaining part after $12321$ has been removed, $abba$ is also a palindrome.

The above indicates the following simple algorithm.

• Compare the letters at the front of $A$ with the corresponding letters at the behind of $B$ one by one so as to find $i_0$, the largest $i\le n/2$ such that $A[:i]+B[-i:]$ is a palindrome.

• Starting from the center of $A$, expand both ways to find the longest palindrome sitting in the central of $A$. Let $c_A$ be its length. If $2i_0 + c_A\ge n$, return yes.

• Starting from the center of $B$, expand both ways to find the longest palindrome sitting in the central of $B$. Let $c_B$ be its length. If $2i_0 + c_B\ge n$, return yes.

• If we have reached here, return no.

Exercise

Given two strings, $A$ and $B$, devise an $O(n)$ algorithm that determines whether $A[:i]+ B[-(n-i):]$ is a palindrome for some $i$, $0\le i \le\text{len}(A)$ and $0\le n-i \le\text{len}(B)$.
(This exercise should be easy if you know Manacher's algorithm.)

StackExchange Computer Science Q#109662, answer score: 3