Editorial : Prefix-Suffix Palindrome (D1 and D2)

This editorial follows model_sol.cpp on D2 (hard version). D1 (easy version) is the same task with smaller limits, so the same algorithm solves both; slower methods may pass D1 only.

Given a string $s$, find a palindrome $t$ of maximum length such that

where $a$ is a (possibly empty) prefix of $s$, and $b$ is a (possibly empty) suffix of $s$.

While the first and last characters of the current window match, advance the left pointer and retreat the right pointer. If $L$ is the number of matched pairs removed this way, those symbols contribute a palindrome of length $2L$ that can sit on the outside of any optimal answer, using only a prefix of $s$ on the left and a suffix of $s$ on the right.

After peeling, write the remaining middle as $m$ (the substring between the two pointers). If $m$ is empty, output the outer part only.

All remaining choices live inside $m$.

Inside $m$, you need a palindrome $t'$ of the form

where $p$ is a prefix of $m$, $q$ is a suffix of $m$, and either side may be empty. You maximize $|t'|$, then output

which remains a palindrome because the two peeled blocks are mirrors of each other.

Write $P_1 = \mathrm{LPP}(m)$ for the longest palindromic prefix of $m$, and $P_2 = \mathrm{LPP}(\mathrm{rev}(m))$ for the longest palindromic prefix of $\mathrm{rev}(m)$ (the same string the second kmp call returns).

Lemma (two-prefix optimality on the peeled middle). Let $\mathcal{F}(m)$ be the maximum length of a palindrome $t' = p + q$ with $p$ a prefix of $m$ and $q$ a suffix of $m$. After the outer peeling loop in main, the middle string $m = s[l..r]$ satisfies either $|m| \le 1$ or

In that second situation, any feasible $t'$ cannot use both a nonempty prefix piece and a nonempty suffix piece: if $|p| > 0$ and $|q| > 0$, then the first symbol of $t'$ is $m_0$ and the last is $m_{|m|-1}$, and a palindrome needs those two symbols to be equal, contradicting $m_0 \neq m_{|m|-1}$.

Therefore:

• if $q$ is empty, $t'$ is a palindromic prefix of $m$, so $|t'| \le |P_1|$;
• if $p$ is empty, $t'$ is a palindromic suffix substring of $m$, hence $\mathrm{rev}(t')$ is a palindromic prefix of $\mathrm{rev}(m)$, so $|t'| \le |P_2|$.

If $|m| \le 1$, both candidates capture the optimum trivially. Both maxima are attainable: $P_1$ uses $q = \varepsilon$; when $p = \varepsilon$, taking $q$ as the length-$|P_2|$ suffix of $m$ whose reverse is the prefix $P_2$ of $\mathrm{rev}(m)$ recovers $P_2$ as a palindrome (so $|t'| = |P_2|$ is feasible). Hence $\mathcal{F}(m) = \max(|P_1|, |P_2|)$ on this middle instance.

The program picks the longer of $P_1$ and $P_2$ (swap on length) and concatenates with the peeled outer pieces.

Remark. Examples such as “abca” are easy to misread if you forget the outer peel: the program never runs kmp on “abca” as a middle; it first reduces to “bc”, where the $m_0 \neq m_{|m| - 1}$ dichotomy is immediate.

For any string $u$, build

with a separator $\texttt{\$}$ that does not appear in $u$. Compute the KMP **prefix function** $\pi$ on $T$. The value $\pi[|T|-1]$ equals the length of the longest border of $T$, which is exactly $| \mathrm{LPP}(u) |$:

• any border must lie entirely in the left $u$ and in the right $\mathrm{rev}(u)$ past the separator, hence is a prefix of $u$ equal to its own reversal.

kmp in model_sol.cpp runs this construction and returns u.substr(0, j) for the final border length $j$.

After reverse(c.begin(), c.end()) on the middle string c, the second kmp call computes $\mathrm{LPP}(\mathrm{rev}(m))$ in the same way.

The algorithm is unchanged; only the efficiency requirement differs.

Two linear passes on a string of length $\Theta(|m|)$ per test case, plus $O(L)$ peeling. With a reused failure array sized for the global length budget, total time is linear in the total input size for D2.

• Outer while: peel matching ends of $s$.
• c = s.substr(l, r - l + 1): middle $m$.
• a = kmp(c): palindrome $P_1$.
• reverse(c); b = kmp(c): palindrome $P_2$ (note c is now $\mathrm{rev}(m)$ in the variable).
• if (a.size() < b.size()) swap(a, b): keep the longer middle palindrome in a.
• Final cout: reattach s[0..l-1] and s[r+1..].