I looked at the editorial but couldn't follow it. Here's my solution.

Prerequisites: Be able to create a suffix array from a string with LCP, be able to make RMQ queries on the LCP array, and implement Manacher's algorithm to find maximum palindromes.

Given two strings A and B, let revB = rev(B), and A' and B' are two substrings in A and revB where A' == B'. Then the solution will be the maximal length of the string where: A' + (palindrome in A after A') + B' OR B' + (palindrome in revB after B') + A'

We can handle both these cases by reversing B and independently finding the best result for A + rev(B) and rev(B) + A.

Let's solve for A, then we can find the final answer by swapping A and rev(B) and returning the best result.

First, we use Manacher's algorithm to give us an array of the max length of the palindromes starting at each index of a string. Manacher's algorithm gives us the maximal length of the palindrome centered at each index of a modified string of the form "|a|b|c|...|", so we can convert that into an array of the the maximal palindromes starting at the indexes of the original string "abc..." by changing coordinates, then fill in all non-maximal values:

fn longest_palindrome_by_start(s: &str) -> Vec<usize> {
    let lps = palindromes(s);
    let mut dp = vec![1; s.len()];
    for (i, &n) in lps.iter().enumerate().take(lps.len() - 1).skip(1) {
	// i:  12345
	// n: 0123210
	// j:  0 1 2
        //    |a|a|a|
        let j = (i - n) / 2;
        dp[j] = dp[j].max(n);
    }

    // dp now has all maximal palindromes by start. Fill in non-maximal values.
    let mut x = 1;
    for i in 0..dp.len() {
        if dp[i] >= x {
            x = dp[i];
        }
        dp[i] = x;
        if x > 2 {
            x -= 2;
        } else if x == 2 {
            x = 1;
        }
    }
    dp
}

Now we have lp = longest_palindrome_by_start(a).

Then, we compute a suffix array with LCP for "a$rev(b)", and a data structure to compute RMQ over the LCP. A solution palindrome looks like (substring of a) + (palidnrome in a after substring) + (substring of a in rev(b)). We have to find the lexicographically least solution palindrome of maximum length.

The suffix array gives us lexicographically ordered suffixes of the combined string "a$rev(b)". For every index in a, we need the maximum length of the common substring between a[i..] and b. To do that in lexicographical order, we maintain two pointers into the suffix array, left and right, which correspond to elements of the suffix array which are both in B. At each step, every element between left and right are all in A. For any i between left and right, the longest common substring between A and B is lcs = max(rmq[left + 1, i], rmq[i + 1, right]). Using this lcs, we can calculate the suffix_palindrome_len = lp[sa[i] + lcs], and the total palindrome length will be 2 * lcs + suffix_palindrome_len. We just track the max palindrome and return the first one which hits the max length:

fn solve_for_a<'a>(a: &'a str, b: &str) -> Option<Palindrome<'a>> {
    let lp = longest_palindrome_by_start(a);
    let combined = a
        .chars()
        .chain(std::iter::once('$'))
        .chain(b.chars())
        .map(|c| c as u8)
        .collect::<Vec<_>>();
    let sa = SuffixArray::new(&combined, 128).with_lcp();
    let rmq = RMQ::new(&sa.lcp);
    let n = a.len();

    let mut max_len = 0;
    let mut max_palindrome = None;

    // Maintain two pointers, left and right, to consecutive elements of sa which are in b.
    // For all elements of sa between left and right, left < i < right,
    // let prefix_len[i] = max(rmq[left + 1, i], rmq[i + 1, right])
    let mut left = sa.sa.iter().position(|&x| x > n).unwrap();
    while left < sa.sa.len() {
        let right = match sa.sa[left + 1..].iter().position(|&x| x > n) {
            Some(x) => left + 1 + x,
            None => sa.sa.len(),
        };
        for i in left + 1..right {
            // all i in a bounded by left and right in b.
            let j = sa.sa[i];
            let mut prefix_len = *rmq.get(left + 1, i);
            if right < sa.sa.len() {
                prefix_len = prefix_len.max(*rmq.get(i + 1, right));
            }
            if prefix_len == 0 {
                // no common substring
                continue;
            }
            let k = j + prefix_len;
            let suffix_len = if k < a.len() { lp[k] } else { 0 };
            let len = 2 * prefix_len + suffix_len;
            if len > max_len {
                max_len = len;

                max_palindrome = Some(Palindrome {
                    prefix: &a[j..k],
                    suffix: &a[k..k + suffix_len],
                });
            }
        }
        left = right;
    }

    max_palindrome
}

Note that we have to do this both for a + rev(b) and rev(b) + a and report out the max by length and lexicographical order.