We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Build a Palindrome
  5. Discussions

Build a Palindrome

Sort by

recency

|

57 Discussions

|

  • jsc
     + 0 comments

    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.

  • axellbrendow
     + 0 comments

    Java, Brute Force TLE version

      public static String buildAPalindrome(String a, String b) {
    String longest = "";
    for (int ai = 0; ai < a.length(); ai++) {
      StringBuilder aBuilder = new StringBuilder();
      for (int aj = ai; aj < a.length(); aj++) {
        aBuilder.append(a.charAt(aj));
        for (int bi = 0; bi < b.length(); bi++) {
          StringBuilder bBuilder = new StringBuilder();
          for (int bj = bi; bj < b.length(); bj++) {
            bBuilder.append(b.charAt(bj));
            String palindrome = aBuilder.toString() + bBuilder.toString();
            if (!palindrome.equals(new StringBuilder(palindrome).reverse().toString())) continue;
            if (
              palindrome.length() > longest.length()
              || (palindrome.length() == longest.length() && palindrome.compareTo(longest) < 0)
            ) {
              longest = palindrome;
            }
          }
        }
      }
    }
    return longest.isEmpty() ? "-1" : longest;
  }

  • phoenixdev100
     + 1 comment

    c++

    #include <bits/stdc++.h>
using namespace std;

inline void wssert(bool b) { if(!b) exit(0); }

const string BAD = "-1";

const int MAXN = 2e5;
const int MAXM = 2e5;
const int MAXL = MAXN * 2 + MAXM * 2 + 20;
int N;
char A[MAXN];
int M;
char B[MAXM];
int L;
char V[MAXL];
int S;

int P[MAXL]; // length of palindrome - 1 / 2
int C[MAXL];

void manacher() {
    int c = 0, r = 0;
    memset(P, 0, sizeof(P));
    for(int i = 0; i < L; ) {
        assert(i - P[i] >= 0);
        assert(i + P[i] < L);
        assert(r == c + P[c]);
        assert(i >= c);
        assert(r >= i + P[i]);
        assert(i == c || r > i + P[i]);
        if(i == c) {
            assert(r == i + P[i]);
            if(i - P[i] - 1 >= 0 && i + P[i] + 1 < L && V[i - P[i] - 1] == V[i + P[i] + 1]) {
                P[i] ++;
                assert(i - P[i] >= 0);
                assert(i + P[i] < L);
            } else {
                i++;
                assert(P[i] == 0);
                assert(i - P[i] >= 0);
                assert(i == L || i + P[i] < L);
            }
       } else {
            assert(i > c);
            assert(r > i + P[i]);
            assert(c - P[c] >= 0);
            assert(c - (i - c) >= 0);
            int v = min(P[c - (i - c)], r - i);
            assert(v >= P[i]);
            if(v > P[i]) {
                P[i] = v;
                assert(i - P[i] >= 0);
                assert(i + P[i] < L);
            } else if (v == r - i) {
                assert(false);
            } else {
                i++;
                assert(P[i] == 0);
                assert(i - P[i] >= 0);
                assert(i == L || i + P[i] < L);
            }
        }
        if(i == L) break;
        if(i + P[i] >= r) {
            c = i;
            r = i + P[i];
        }
        assert(i - P[i] >= 0);
        assert(i + P[i] < L);
    }
}

#define REP(i, n) for(int i = 0; i < int(n); i++)
int gap;
int sa[MAXL], pos[MAXL], tmp[MAXL], lcp[MAXL];

bool sufCmp(int i, int j)
{
    if (pos[i] != pos[j])
        return pos[i] < pos[j];
    i += gap;
    j += gap;
    return (i < L && j < L) ? pos[i] < pos[j] : i > j;
}

void buildSA()
{
    REP(i, L) sa[i] = i, pos[i] = V[i];
    for (gap = 1;; gap *= 2)
    {
        sort(sa, sa + L, sufCmp);
        REP(i, L - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
        REP(i, L) pos[sa[i]] = tmp[i];
        if (tmp[L - 1] == L - 1) break;
    }
}

void buildLCP()
{
    for (int i = 0, k = 0; i < L; ++i) if (pos[i] != L - 1)
    {
        for (int j = sa[pos[i] + 1]; V[i + k] == V[j + k];)
            ++k;
        lcp[pos[i]] = k;
        if (k)--k;
    }
}

string process(int l, int c) {
    string res;
    for(int i = l; i < c; i++) {
        if(V[i] != 124) res += V[i];
    }
    for(int i = c; i >= l; i--) {
        if(V[i] != 124) res += V[i];
    }
    return res;
}

string go() {
    manacher();
    for(int i = 0; i < L; i++) {
        assert(!(i - P[i] - 1 >= 0 && i + P[i] + 1 < L && V[i - P[i] - 1] == V[i + P[i] + 1]));
        //for(int j = 0; j <= P[i]; j++) assert(V[i - j] == V[i + j]);
    }
    memset(C, 0, sizeof(C));
    for(int i = 0; i < L; i++) {
        C[i - P[i]] = max(C[i - P[i]], i);
    }
    for(int i = 1; i < L; i++) {
        C[i] = max(C[i], C[i - 1]);
    }
    buildSA();
    buildLCP();
    for(int i = 0; i < L; i++) {
        //cerr << (V + sa[i]) << '\n';
    }
    for(int i = 0; i + 1 < L; i++) {
        //for(int j = 0; j < lcp[i]; j++) assert(V[sa[i] + j] == V[sa[i + 1] + j]);
        assert(V[sa[i] + lcp[i]] < V[sa[i + 1] + lcp[i]]);
    }
    assert(V[sa[N + M]] == 123);
    int p[2] = {-1, -1};
    int l[2] = {0, 0};
    pair<int, int> res (0, 0);
    for(int i = 0; i < N + M; i++) {
        assert(V[sa[i]] < 123);
        bool d = (sa[i] >= S);
        p[d] = sa[i];
        l[d] = L;
        if(p[!d] != -1) {
            int match = l[!d];
            assert(match % 2 == 0);
            //cerr << p[!d] << ' ' << p[d] << ' ' << match << '\n';
            if(match) res = max(res, make_pair(C[sa[i] + match - 1] - sa[i], -i));
        }
        if(i + 1 < L) l[0] = min(lcp[i], l[0]), l[1] = min(lcp[i], l[1]);
    }
    p[0] = p[1] = -1;
    l[0] = l[1] = -1;
    for(int i = N + M - 1; i >= 0; i--) {
        bool d = (sa[i] >= S);
        p[d] = sa[i];
        l[d] = L;
        if(p[!d] != -1) {
            int match = l[!d];
            assert(match % 2 == 0);
            if(match) res = max(res, make_pair(C[sa[i] + match - 1] - sa[i], -i));
        }
        if(i > 0) l[0] = min(lcp[i - 1], l[0]), l[1] = min(lcp[i-1], l[1]);
    }
    //cerr << res << '\n';
    if(res.first == 0) return BAD;
    return process(sa[-res.second], sa[-res.second] + res.first);
}

int main() {
    int Q; cin >> Q;
    while(Q --> 0) {
        cin >> A >> B;
        N = strlen(A), M = strlen(B);
        L = 0;
        for(int i = 0; i < N; i++) {
            V[L++] = A[i];
            V[L++] = 124;
        }
        V[L++] = 123;
        V[L++] = 125;
        S = L;
        for(int i = M - 1; i >= 0; i--) {
            V[L++] = B[i];
            V[L++] = 124;
        }
        V[L] = 0;
        assert(L == 2 * N + 2 * M + 2);
        cout << go() << '\n';
    }
    return 0;
}

  • kaustubh872
     + 1 comment

    any alternative to using LCS table? Because using LCS table for longer inputs, abort gets called. The solution which without table i am thinking is very complicated

  • tim_busfield
     + 1 comment

    Why when combining "bac" and "bac" is the answer not "abcba"?