Header Ad

HackerRank Build a Palindrome problem solution

In this HackerRank Build a Palindrome problem solution we have given two strings a and b and we need to find a string so that string is equal to the addition of substrings of a and b means we need to find and print a string on a new line and if have more than one valid string then we need to print whichever one comes first alphabetically and if there is no valid answer then print -1 instead.

HackerRank Build a Palindrome problem solution


Problem solution in Python.

def build_palindrome_lookup(s):
    sx = '|' + '|'.join(s) + '|'
    sxlen = len(sx)
    rslt = [0] * sxlen
    c, r, m, n = 0, 0, 0, 0
    for i in range(1, sxlen):
        if i > r:
            rslt[i] = 0
            m = i - 1
            n = i + 1
        else:
            i2 = c * 2 - i
            if rslt[i2] < r - i:
                rslt[i] = rslt[i2]
                m = -1
            else:
                rslt[i] = r - i
                n = r + 1
                m = i * 2 - n
        while m >= 0 and n < sxlen and sx[m] == sx[n]:
            rslt[i] += 1
            m -= 1
            n += 1
        if i + rslt[i] > r:
            r = i + rslt[i]
            c = i
    res = [0] * len(s)
    for i in range(1, sxlen - 1):
        idx = (i - rslt[i]) // 2
        res[idx] = max(res[idx], rslt[i])
    return res

class state:
    def __init__(self):
        self.link = -1
        self.length = 0
        self.childs = {}

def build_part_st(a, st, num, last, sz):
    for c in a:
        cur = sz
        sz += 1
        st[cur].length = st[last].length + 1
        p = last
        while p != -1 and c not in st[p].childs:
            st[p].childs[c] = cur
            p = st[p].link
        if p == -1:
            st[cur].link = 0
        else:
            q = st[p].childs[c]
            if st[p].length + 1 == st[q].length:
                st[cur].link = q
            else:
                clone = sz
                sz += 1
                st[clone].length = st[p].length + 1
                st[clone].childs = dict((x, y) for (x, y) in st[q].childs.items())
                st[clone].link = st[q].link
                while p != -1 and st[p].childs[c] == q:
                    st[p].childs[c] = clone
                    p = st[p].link
                st[q].link = clone
                st[cur].link = clone
        last = cur
    return last, sz

def print_st(st):
    i = 0
    for s in st:
        print('#{} link:{} childs:{}'.format(i, s.link, s.childs))
        i += 1

def solve(a, b):
    n = len(a)
    blen = len(b)
    st = [state() for x in range(2 * n)]
    st[0].link = -1
    st[0].length = 0
    last = 0
    sz = 1
    last, sz = build_part_st(a, st, 1, last, sz)
    plookup = build_palindrome_lookup(b)
    apos, start, left, mid, total, curlen = 0, -1, 0, 0, 0, 0
    for i in range(blen):
        c = b[i]
        if c not in st[apos].childs:
            while apos!=-1 and c not in st[apos].childs:
                apos = st[apos].link
            if apos == -1:
                apos = 0
                curlen=0
                continue
            curlen = st[apos].length
        curlen += 1
        apos = st[apos].childs[c]
        new_start = i - curlen + 1
        new_mid = 0
        if i + 1 < blen:
           new_mid = plookup[i + 1]
        new_total = 2 * curlen + new_mid
        if total < new_total or (total == new_total and lex_gt(b,start, new_start,curlen + mid)):
            left = curlen
            mid = new_mid
            total = new_total
            start = new_start
    palindrome = []
    for i in range(left + mid):
        palindrome.append(b[start + i])
    for i in range(left - 1, -1, -1):
        palindrome.append(palindrome[i])
    return ''.join(palindrome)
        
def lex_gt(s, old_start, new_start, size):
    for i in range(size):
        if s[old_start + i] != s[new_start + i]:
            if s[old_start + i] > s[new_start + i]:# old lex greater so pick new one
                return True
            break
    return False

def suffix_automata(a,b):
    rb = b[::-1] # reverse b
    rslt1 = solve(a, rb)
    rslt2 = solve(rb, a)
    rslt = None
    if len(rslt1) > len(rslt2):
        rslt = rslt1
    elif len(rslt1) < len(rslt2):
        rslt = rslt2
    else:
        rslt= rslt1 if rslt1 < rslt2 else rslt2
    if len(rslt) == 0:
        return '-1'
    return rslt

def process_helper(a,b):
    return suffix_automata(a,b)

for _ in range(int(input())):
    a = input()
    b = input()
    print(process_helper(a,b))

{"mode":"full","isActive":false}


Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static int N = 100000;
  static int M = 4 * N + 3;
  static char[] a = new char[M];
  static int[] sa = new int[M];
  static int[] isa = new int[M];

  static void iota(int v[], int end, int val) {
    for (int i = 0; i < end; i++) {
      v[i] = val++;
    }
  }

  static void suffixArray(int n, int m, int h[], int x[]) {
    Arrays.fill(h, 0, m, 0);
    for (int i = 0; i < n; i++) {
      isa[i] = a[i];
    }
    for (int i = 0; i < n; i++) {
      h[isa[i]]++;
    }
    for (int i = 1; i < m; i++) {
      h[i] += h[i - 1];
    }
    for (int i = n; --i >= 0;) {
      sa[--h[isa[i]]] = i;
    }
    int k = 1;
    for (;; k <<= 1) {
      iota(x, k, n - k);
      int j = k;
      for (int i = 0; i < n; i++) {
        if (sa[i] >= k) {
          x[j++] = sa[i] - k;
        }
      }
      Arrays.fill(h, 0, m, 0);
      for (int i = 0; i < n; i++) {
        h[isa[x[i]]]++;
      }
      for (int i = 1; i < m; i++) {
        h[i] += h[i - 1];
      }
      for (int i = n; --i >= 0;) {
        sa[--h[isa[x[i]]]] = x[i];
      }
      Arrays.fill(h, 0, m, 0);
      m = 1;
      h[sa[0]] = 0;
      for (int i = 1; i < n; i++) {
        if (isa[sa[i]] != isa[sa[i - 1]] || Math.max(sa[i], sa[i - 1]) >= n - k
            || isa[sa[i] + k] != isa[sa[i - 1] + k]) {
          m++;
        }
        h[sa[i]] = m - 1;
      }
      System.arraycopy(h, 0, isa, 0, n);
      if (m == n) {
        break;
      }
    }
    k = 0;
    h[0] = 0;
    for (int i = 0; i < n; i++) {
      if (isa[i] > 0) {
        for (int j = sa[isa[i] - 1]; i + k < n && j + k < n && a[i + k] == a[j + k]; k++)
          ;
        h[isa[i]] = k;
        if (k > 0) {
          k--;
        }
      }
    }
  }

  static int[][] tab = new int[19][M];

  static int lcp(int x, int y) {
    if (x < 0 || y < 0) {
      return 0;
    }
    x = isa[x];
    y = isa[y];
    if (x > y) {
      int t = x;
      x = y;
      y = t;
    }
    x++;
    int k = 0;
    while (1 << k + 1 < y - x + 1) {
      k++;
    }
    return Math.min(tab[k][x], tab[k][y - (1 << k) + 1]);
  }

  static long[] z = new long[2 * N + 1];
  static int[] len = new int[N];
  
  static void manacher(int from, int n) {
    int m = 2 * n + 1;
    z[0] = 1;
    for (int f = 0, g = 0, i = 1; i < m; i++) {
      if (i < g && z[2 * f - i] != g - i) {
        z[i] = Math.min(z[2 * f - i], g - i);
      } else {
        g = Math.max(g, f = i);
        for (; g < m && 2 * f - g >= 0 && (g % 2 == 0 || a[from + (2 * f - g) / 2] == a[from + g / 2]); g++) {
          len[(g - 1) / 2] = g - f;
        }
        z[f] = g - f;
      }
    }
  }

  static int[] L = new int[M];
  static int[] R = new int[M];

  static char[] buildPalindrome(char[] a1, char[] b) {
    int na = a1.length;
    System.arraycopy(a1, 0, a, 0, na);
    a[na] = 0;
    int ra = na + 1;
    for (int i = 0; i < na; i++) {
      a[ra + i] = a[na - 1 - i];
    }
    a[ra + na] = 1;
    int nb = b.length;
    int b0 = ra + na + 1;
    System.arraycopy(b, 0, a, b0, nb);
    a[b0 + nb] = 2;
    int rb = b0 + nb + 1;
    for (int i = 0; i < nb; i++) {
      a[rb + i] = b[nb - 1 - i];
    }
    int n = 2 * na + 2 * nb + 3;
    suffixArray(n, 'z' + 1, tab[0], L);
    for (int i = 1; 1 << i < n; i++) {
      for (int j = n - (1 << i); j > 0; j--) {
        tab[i][j] = Math.min(tab[i - 1][j], tab[i - 1][j + (1 << i - 1)]);
      }
    }
    int bma = na + 1 + na + 1;
    for (int i = 0; i < n; i++) {
      if (bma <= sa[i] && sa[i] < bma + nb) {
        L[i] = sa[i];
      } else {
        L[i] = i > 0 ? L[i - 1] : -1;
      }
    }
    for (int i = n; --i >= 0;) {
      if (bma <= sa[i] && sa[i] < bma + nb) {
        R[i] = sa[i];
      } else {
        R[i] = i + 1 < n ? R[i + 1] : -1;
      }
    }
    manacher(na + 1, na);
    int opt = 0;
    int optp = 0;
    int optx = 0;
    int opty = 0;
    
    for (int i = 0; i < na; i++) {
      int pal = i > 0 ? len[i - 1] : 0;
      int ii = na + 1 + i;
      int j = L[isa[ii]];
      if (lcp(ii, R[isa[ii]]) > lcp(ii, j))
        j = R[isa[ii]];
      int comm = lcp(ii, j);
      if (comm > 0) {
        int len = pal + 2 * comm;
        int pos = na - (i + comm);
        if (len > opt || len == opt && isa[pos] < isa[optp]) {
          opt = len;
          optp = pos;
          optx = pal + comm;
          opty = comm;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      if (na + 1 <= sa[i] && sa[i] < na + 1 + na) {
        L[i] = sa[i];
      } else {
        L[i] = i > 0 ? L[i - 1] : -1;
      }
    }
    for (int i = n; --i >= 0;) {
      if (na + 1 <= sa[i] && sa[i] < na + 1 + na) {
        R[i] = sa[i];
      } else {
        R[i] = i + 1 < n ? R[i + 1] : -1;
      }
    }
    manacher(bma, nb);
    for (int i = 0; i < nb; i++) {
      int pal = i > 0 ? len[i - 1] : 0;
      int ii = bma + i;
      int j = L[isa[ii]];
      if (lcp(ii, R[isa[ii]]) > lcp(ii, j)) {
        j = R[isa[ii]];
      }
      int comm = lcp(ii, j);
      if (comm > 0) {
        int len = pal + 2 * comm, pos = n - (i + comm);
        if (len > opt || len == opt && isa[pos] < isa[optp]) {
          opt = len;
          optp = pos;
          optx = comm;
          opty = pal + comm;
        }
      }
    }

    if (opt == 0) {
      return "-1".toCharArray();
    }
    char[] result = new char[optx + opty];
    for (int i = 0; i < optx; i++) {
      result[i] = a[optp + i];
    }
    for (int i = 0; i < opty; i++) {
      result[optx + i] = a[optp + opty - i - 1];
    }
    return result;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());

    for (int tItr = 0; tItr < t; tItr++) {
      char[] a = br.readLine().toCharArray();
      char[] b = br.readLine().toCharArray();

      bw.write(buildPalindrome(a, b));
      bw.newLine();
    }

    bw.close();
    br.close();
  }
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#include <bits/stdc++.h>



#ifndef SUFFIXARRAY_H_INCLUDED
#define SUFFIXARRAY_H_INCLUDED



class suffix_array
{
public:
    std::vector<int> suftab[2];
    std::vector<int> order;
    std::vector<int> sufarr;
    std::vector<int> bucket_count, bucket_size;
    std::vector<int> lcp; // lcp(sa[i], sa[i+1]) == sa.lcp[i]
    template<class T>
    void build_sa(T S[], int N)
    {
        suftab[0].resize(N);
        suftab[1].resize(N);
        order.resize(N);
        sufarr.resize(N);
        bucket_count.resize(N+1);
        bucket_size.resize(N+1);
        for(int i=0; i<N; i++)
            order[i]=S[i];
        std::sort(order.begin(), order.end());
        for(int i=0; i<N; i++)
            suftab[0][i]=std::lower_bound(order.begin(), order.end(), S[i])-order.begin();
        int lg=0;
        while((1<<lg)<N)
            lg++;
        int row=0;
        for(int hlen=1; hlen<(1<<lg); hlen*=2, row^=1)
        {
            bucket_count.assign(N+1, 0);
            int pos=0;
            for(int i=0; i+hlen<N; i++)
                bucket_count[suftab[row][i+hlen]+1]++;
            for(int i=N-hlen; i<N; i++)
                order[pos++]=i;
            bucket_count[0]=pos;
            std::partial_sum(bucket_count.begin(), bucket_count.end(), bucket_size.begin());
            for(int i=0; i+hlen<N; i++)
                order[bucket_size[suftab[row][i+hlen]]++]=i;
            bucket_count[0]=0;
            for(int i=0; i<hlen; i++)
                bucket_count[suftab[row][i]+1]++;
            std::partial_sum(bucket_count.begin(), bucket_count.end(), bucket_size.begin());
            for(int i=0; i<N; i++)
                sufarr[bucket_size[suftab[row][order[i]]]++]=order[i];
            int prev_a=-1, prev_b=-1, prev_c=-1;
            for(int i=0; i<N; i++)
            {
                const int x=sufarr[i];
                const int now_a=suftab[row][x];
                const int now_b=(x+hlen<N?suftab[row][x+hlen]:-1);
                prev_c+=now_a!=prev_a || now_b!=prev_b;
                suftab[row^1][x]=prev_c;
                prev_a=now_a;
                prev_b=now_b;
            }
        }
        if(row==1)
            suftab[0].swap(suftab[1]);
    }
    template<class T>
    void build(T S[], int N)
    {
        build_sa(S, N);
        lcp.resize(sufarr.size());
        for(int i=0, len=0; i<N; i++)
        {
            if(get_rank(i)==N-1)
                len=0;
            else
            {
                int j=sufarr[get_rank(i)+1];
                int maxl=N-std::max(i, j);
                while(len<maxl && S[i+len]==S[j+len])
                    len++;
                lcp[get_rank(i)]=len;
                if(len>0)
                    len--;
            }
        }
    }
    inline int get_rank(const int& idx) const
    {
        return suftab[0][idx];
    }
    int operator[] (const int& idx) const
    {
        return sufarr[idx];
    }
};

#endif // SUFFIXARRAY_H_INCLUDED

const int HASH_MAXN=400001;
const int X=129;
const int MOD1=1000000009;
const int MOD2=1000000021;
int P1[HASH_MAXN];
int P2[HASH_MAXN];

struct Hash
{
    int len, val0, val1;
    Hash():
        len(0),
        val0(0),
        val1(0)
    {
        //
    }
    Hash(int val):
        len(1),
        val0(val),
        val1(val)
    {
        //
    }
    Hash operator+ (const Hash& other) const
    {
        Hash ret;
        ret.len=len+other.len;
        ret.val0=(other.val0+1LL*P1[other.len]*val0)%MOD1;
        ret.val1=(other.val1+1LL*P2[other.len]*val1)%MOD2;
        return ret;
    }
    Hash operator- (const Hash& other) const
    {
        Hash ret;
        ret.len=len-other.len;
        ret.val0=val0-1LL*P1[len-other.len]*other.val0%MOD1;
        if(ret.val0<0)
            ret.val0+=MOD1;
        ret.val1=val1-1LL*P2[len-other.len]*other.val1%MOD2;
        if(ret.val1<0)
            ret.val1+=MOD2;
        return ret;
    }
    bool operator< (const Hash& other) const
    {
        if(len!=other.len)
            return len<other.len;
        if(val0!=other.val0)
            return val0<other.val0;
        return val1<other.val1;
    }
    bool operator== (const Hash& other) const
    {
        return len==other.len && val0==other.val0 && val1==other.val1;
    }
    bool operator!= (const Hash& other) const
    {
        return !(*this==other);
    }
};

void init_hash()
{
    P1[0]=1;
    for(int i=1; i<HASH_MAXN; i++)
        P1[i]=1LL*P1[i-1]*X%MOD1;
    P2[0]=1;
    for(int i=1; i<HASH_MAXN; i++)
        P2[i]=1LL*P2[i-1]*X%MOD2;
}

static int _hash_initialized=(init_hash(), 0);

int tlen;
int msuf[200001];
Hash H[200001];
Hash R[200001];

Hash get_substr(int l, int r)
{
    if(l==0)
        return H[r];
    return H[r]-H[l-1];
}

Hash get_r_substr(int l, int r)
{
    if(r==tlen-1)
        return R[l];
    return R[l]-R[r+1];
}

Hash get_hash(vector<pair<int, int>>& a, int l)
{
    Hash h;
    for(auto& it: a)
    {
        if(l==0)
            break;
        if(abs(it.first-it.second)+1<=l)
        {
            l-=abs(it.first-it.second)+1;
            if(it.first>it.second)
                h=h+get_r_substr(it.second, it.first);
            else
                h=h+get_substr(it.first, it.second);
        }
        else
        {
            if(it.first>it.second)
                h=h+get_r_substr(it.first-l+1, it.first);
            else
                h=h+get_substr(it.first, it.first+l-1);
            break;
        }
    }
    return h;
}

char get_char(string& t, vector<pair<int, int>>& a, int l)
{
    for(auto& it: a)
    {
        if(abs(it.first-it.second)+1<=l)
            l-=abs(it.first-it.second)+1;
        else
        {
            if(it.first>it.second)
                return t[it.first-l];
            return t[it.first+l];
        }
    }
    return '?';
}

vector<pair<int, int>> get_min(string& t, vector<pair<int, int>> a, vector<pair<int, int>> b)
{
    int la=0, lb=0;
    for(auto& it: a)
        la+=abs(it.first-it.second)+1;
    for(auto& it: b)
        lb+=abs(it.first-it.second)+1;
    assert(la==lb);
    int lo=0, mid, hi=min(la, lb);
    while(lo<hi)
    {
        mid=(lo+hi+1)/2;
        if(get_hash(a, mid)==get_hash(b, mid))
            lo=mid;
        else
            hi=mid-1;
    }
    if(lo==min(la, lb) || get_char(t, a, lo)<get_char(t, b, lo))
        return a;
    return b;
}

pair<int, string> solve(string s, string t)
{
    tlen=t.length();
    reverse(s.begin(), s.end());
    string S=t+'#'+s;
    suffix_array sa;
    sa.build(S.c_str(), S.length());
    for(int i=0; i<=(int)t.length(); i++)
        msuf[i]=0;
    int len=0;
    for(int i=0; i<(int)S.length(); i++)
    {
        int suf=sa[i];
        if(suf<(int)t.length())
            msuf[suf]=max(msuf[suf], len);
        else if(suf>(int)t.length() && i+1<(int)S.length())
            len=max(len, sa.lcp[i]);
        if(i+1<(int)S.length())
            len=min(len, sa.lcp[i]);
    }
    len=0;
    for(int i=(int)S.length()-1; i>=0; i--)
    {
        int suf=sa[i];
        if(suf<(int)t.length())
            msuf[suf]=max(msuf[suf], len);
        else if(suf>(int)t.length() && i-1>=0)
            len=max(len, sa.lcp[i-1]);
        if(i-1>=0)
            len=min(len, sa.lcp[i-1]);
    }
    Hash h;
    for(int i=0; i<(int)t.length(); i++)
    {
        h=h+Hash(t[i]);
        H[i]=h;
    }
    h=Hash();
    for(int i=(int)t.length()-1; i>=0; i--)
    {
        h=h+Hash(t[i]);
        R[i]=h;
    }
    vector<pair<int, int>> ans2;
    int ans=0;
    for(int i=0; i<(int)t.length(); i++) if(msuf[i])
    {
        if(msuf[i]*2>ans)
        {
            ans=msuf[i]*2;
            ans2={{i, i+msuf[i]-1}, {i+msuf[i]-1, i}};
        }
        else if(msuf[i]*2==ans)
            ans2=get_min(t, ans2, {{i, i+msuf[i]-1}, {i+msuf[i]-1, i}});
    }
    // one center
    for(int i=0; i<(int)t.length(); i++)
    {
        int l=min(i+1, (int)t.length()-i);
        int lo=1, mid, hi=l;
        while(lo<hi)
        {
            mid=(lo+hi+1)/2;
            if(get_r_substr(i-mid+1, i)==get_substr(i, i+mid-1))
                lo=mid;
            else
                hi=mid-1;
        }
        if(msuf[i+lo])
        {
            int v=2*lo-1+2*msuf[i+lo];
            if(v>ans)
            {
                ans=v;
                ans2={{i+lo+msuf[i+lo]-1, i+lo}, {i-lo+1, i+lo+msuf[i+lo]-1}};
            }
            else if(v==ans)
                ans2=get_min(t, ans2, {{i+lo+msuf[i+lo]-1, i+lo}, {i-lo+1, i+lo+msuf[i+lo]-1}});
        }
    }
    // two centers
    for(int i=0; i<(int)t.length()-1; i++)
    {
        int l=min(i+1, (int)t.length()-(i+1));
        int lo=0, mid, hi=l;
        while(lo<hi)
        {
            mid=(lo+hi+1)/2;
            if(get_r_substr(i-mid+1, i)==get_substr(i+1, i+1+mid-1))
                lo=mid;
            else
                hi=mid-1;
        }
        if(msuf[i+1+lo])
        {
            int v=2*lo+2*msuf[i+1+lo];
            if(v>ans)
            {
                ans=v;
                ans2={{i+1+lo+msuf[i+1+lo]-1, i+1+lo}, {i-lo+1, i+1+lo+msuf[i+1+lo]-1}};
            }
            else if(v==ans)
                ans2=get_min(t, ans2, {{i+1+lo+msuf[i+1+lo]-1, i+1+lo}, {i-lo+1, i+1+lo+msuf[i+1+lo]-1}});
        }
    }
    string res="";
    for(auto& it: ans2)
    {
        if(it.first>it.second)
        {
            for(int i=it.first; i>=it.second; i--)
                res+=t[i];
        }
        else
        {
            for(int i=it.first; i<=it.second; i++)
                res+=t[i];
        }
    }
    return make_pair(ans, res);
}

string _main()
{
    string a, b;
    cin>>a>>b;
    if(a.length()<=50 && b.length()<=50)
    {
        string ans="";
        for(int la=1; la<=(int)a.length(); la++)
        {
            for(int i=0; i+la-1<(int)a.length(); i++)
            {
                for(int lb=1; lb<=(int)b.length(); lb++)
                {
                    for(int j=0; j+lb-1<(int)b.length(); j++)
                    {
                        string s=a.substr(i, la)+b.substr(j, lb);
                        string t=s;
                        reverse(t.begin(), t.end());
                        if(s==t)
                        {
                            if(s.length()>ans.length())
                                ans=s;
                            else if(s.length()==ans.length())
                                ans=min(ans, s);
                        }
                    }
                }
            }
        }
        if(ans.empty())
            return "-1";
        return ans;
    }
    auto x=solve(a, b);
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    auto y=solve(b, a);
    reverse(y.second.begin(), y.second.end());
    if(max(x.first, y.first)==0)
        return "-1";
    if(x.first>y.first)
        return x.second;
    else if(x.first<y.first)
        return y.second;
    return min(x.second, y.second);
}

int main()
{
    int Q;
    scanf("%d", &Q);
    while(Q--)
        cout<<_main()<<endl;
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>
#define SWAP(_X, _Y, __type)    \
    do{                        \
        __type __tmp = _X;      \
        _X = _Y;                \
        _Y = __tmp;             \
    }while(0)
#define MAX(__X, __Y) ((__X) > (__Y) ? (__X) : (__Y))
#define MIN(__X, __Y) ((__X) < (__Y) ? (__X) : (__Y))
struct interval
{
    int mid;
    int odd;
    int begin;
    int end;
};
int icmp(const void *p1, const void *p2)
{
    const struct interval *i1 = p1;
    const struct interval *i2 = p2;
    if( i1 -> begin < i2 -> begin )
    {
        return -1;
    }
    else if( i1 -> begin > i2 -> begin )
    {
        return 1;
    }
    return 0;
}
int *_find_longest_palindromes(int *radius[2], int len)
{
    int *result;
    struct interval *intervals;
    int num_intervals = 0;
    result = malloc(sizeof(*result) * len);
    for( int i = 0 ; i < len ; ++i )
    {
        result[i] = 1;
    }
    intervals = malloc(sizeof(*intervals) * len * 2);
    for( int j = 0 ; j < 2 ; ++j )
    {
        for( int i = 0 ; i < len ; ++i )
        {
            if( radius[j][i] != 0 )
            {
                intervals[num_intervals].odd = j;
                intervals[num_intervals].mid = i;
                intervals[num_intervals].begin = intervals[num_intervals].mid - radius[j][i];
                intervals[num_intervals].end = intervals[num_intervals].mid - 1;
                ++num_intervals;
            }
        }
    }
    if( num_intervals > 0 )
    {
        int _num_intervals = 1;
        qsort(intervals, num_intervals, sizeof(*intervals), icmp);
        for( int i = 1 ; i < num_intervals ; ++i )
        {
            if( intervals[_num_intervals - 1].end < intervals[i].begin )
            {
                intervals[_num_intervals++] = intervals[i];
            }
            else if( intervals[_num_intervals - 1].end <= intervals[i].end )
            {
                if( intervals[i].begin == intervals[_num_intervals - 1].begin && ( intervals[_num_intervals - 1].end < intervals[i].end || intervals[i].odd ) )
                {
                    intervals[_num_intervals - 1] = intervals[i];
                }
                else
                {
                    intervals[_num_intervals - 1].end = intervals[i].begin - 1;
                    intervals[_num_intervals++] = intervals[i];
                }
            }
        }
        num_intervals = _num_intervals;
    }
    for( int i = 0 ; i < num_intervals ; ++i )
    {
        for( int j = intervals[i].begin ; j <= intervals[i].end ; ++j )
        {
            result[j] = 2 * ( intervals[i].mid - j ) + intervals[i].odd;
        }
    }
    free(intervals);
    return result;
}
int* find_longest_palindromes(const char *s, int len)
{
    int *result, *radius[2];
    radius[0] = malloc(sizeof(int) * len);
    radius[1] = malloc(sizeof(int) * len);
    radius[0][0] = radius[1][0] = 0;
    for( int j = 0 ; j < 2 ; ++j )
    {
        int i = 1, r = 0;
        while( i < len )
        {
            int k = 1;
            if( s[i] != 0x60 )
            {
                for( register int left = i - r - 1, right = i + r + j ; left >= 0 && right < len && s[left] == s[right] ; --left, ++right, ++r );
                radius[j][i] = r;
            }
            else
            {
                radius[j][i] = r = 0;
            }
            while( k < r && radius[j][i - k] != r - k )
            {
                radius[j][i + k] = MIN(radius[j][i - k], r - k);
                ++k;
            }
            r = r > k ? r - k : 0;
            i += k;
        }
    }
    result = _find_longest_palindromes(radius, len);
    free(radius[0]);
    free(radius[1]);
    return result;
}
int * LCP(const char *s, int len, int *sa)
{
    int k = 0;
    int *lcp, *rank;
    lcp = calloc(len, sizeof(*lcp));
    rank = calloc(len, sizeof(*rank));
    for( int i = 0 ; i < len ; ++i )
    {
        rank[sa[i]] = i;
    }
    for( int i = 0 ; i < len ; ++i )
    {
        if( rank[i] == len - 1 )
        {
            k = 0;
        }
        else
        {
            int j = sa[rank[i] + 1];
            while( i + k < len && j + k < len && s[i+k] == s[j+k] )
            {
                k++;
            }
            lcp[rank[i]] = k;
        }
        if( k != 0 )
        {
            --k;
        }
    }
    free(rank);
    return lcp;
}
struct state
{
    int suffix;
    int bucket[2];
};
int * SA(const char *s, int len)
{
    int *p = malloc(sizeof(int) * len);
    int *sa = malloc(sizeof(int) * len);
    struct state *state, *tmp;
    state = malloc(sizeof(*state) * len);
    tmp = malloc(sizeof(*tmp) * len);
    for( int i = 0 ; i < len ; ++i )
    {
        p[i] = s[i] - 0x60 + 1;
    }
    for( int h = 1 ; h < len ; h <<= 1 )
    {
        for( int i = 0 ; i < len ; ++i )
        {
            state[i].suffix = i;
            state[i].bucket[0] = p[i];
            if( i + h < len )
            {
                state[i].bucket[1] = p[i+h];
            }
            else
            {
                state[i].bucket[1] = 0;
            }
        }
        for( int i = 1 ; i >= 0 ; --i )
        {
            for( int div = 1 ; MAX(len, 28) / div > 0 ; div *= 10 )
            {
                int count[10] = {0};
                for( int j = 0 ; j < len ; ++j )
                {
                    ++count[(state[j].bucket[i] / div) % 10];
                }
                for( int j = 1 ; j < 10 ; ++j )
                {
                    count[j] += count[j-1];
                }
                for( int j = len - 1 ; j >= 0 ; --j )
                {
                    register int index = ( state[j].bucket[i] / div ) % 10;
                    tmp[--count[index]] = state[j];
                }
                SWAP(tmp, state, struct state *);
            }
        }
        for( int i = 0, bucket = 0 ; i < len ; ++i )
        {
            if( ( h << 1 ) >= len || i == 0 || state[i-1].bucket[0] != state[i].bucket[0] || state[i-1].bucket[1] != state[i].bucket[1] )
            {
                ++bucket;
            }
            p[state[i].suffix] = bucket;
        }
    }
    free(state);
    free(tmp);
    for( int i = 0 ; i < len ; ++i )
    {
        sa[p[i]-1] = i;
    }
    free(p);
    return sa;
}
char *build_palindrome(const char *a, const char *b)
{
    int alen = strlen(a), blen = strlen(b), *sa, *lcp, *p, *lcp_ab, maxlen = 0, suffix = -1;
    char *result = NULL;
    int slen = alen + blen + 1;
    char *s = malloc(sizeof(char) * ( slen + 1 ));
    memcpy(s, a, alen);
    s[alen] = 0x60;
    for( int i = 0 ; i < blen ; ++i )
    {
        s[alen+1+i] = b[blen-1-i];
    }
    s[slen] = '\0';
    sa = SA(s, slen);
    lcp = LCP(s, slen, sa);
    lcp_ab = calloc(slen, sizeof(*lcp_ab));
    int i = 1;
    while( i < slen - 1 )
    {
        if( lcp[i] && ( ( sa[i] > alen && sa[i+1] < alen ) || ( sa[i] < alen && sa[i+1] > alen ) ) )
        {
            int j, current = lcp[i];
            for( j = i ; j > 0 && ( ( sa[i] > alen ) ? ( sa[j] > alen ) : ( sa[j] < alen ) ) && lcp[j] > 0 ; --j )
            {
                current = MIN(current, lcp[j]);
                lcp_ab[j] = MAX(lcp_ab[j], current);
            }
            current = lcp[i];
            for( j = i + 1 ; j < slen && ( ( sa[i] > alen ) ? ( sa[j] < alen ) : ( sa[j] > alen ) ) && lcp[j-1] > 0 ; ++j )
            {
                lcp_ab[j] = current = MIN(current, lcp[j - 1]);
            }
            i = j - 1;
        }
        else
        {
            ++i;
        }
    }
    p = find_longest_palindromes(s, slen);
    for( int i = 1 ; i < slen ; ++i )
    {
        if(lcp_ab[i])
        {
            int len = 2 * lcp_ab[i];
            if( ( sa[i] < alen && sa[i] + lcp_ab[i] < alen ) || ( sa[i] > alen && sa[i] + lcp_ab[i] < slen ) )
            {
                len += p[sa[i] + lcp_ab[i]];
            }
            if( len > maxlen )
            {
                suffix = i;
                maxlen = len;
            }
        }
    }
    if(maxlen)
    {
        int len = 0;
        result = malloc(sizeof(*result) * ( maxlen + 1 ));
        memcpy(result, s + sa[suffix], lcp_ab[suffix]);
        if( maxlen > lcp_ab[suffix] * 2 )
        {
            memcpy(result + lcp_ab[suffix], s + sa[suffix] + lcp_ab[suffix], maxlen - lcp_ab[suffix] * 2);
        }
        for( int i = 0 ; i < lcp_ab[suffix] ; ++i )
        {
            result[maxlen-lcp_ab[suffix]+i] = s[sa[suffix] + lcp_ab[suffix]-1-i];
        }
        result[maxlen] = '\0';
    }
    free(sa);
    free(lcp);
    free(lcp_ab);
    free(p);
    free(s);
    return result;
}
int main()
{
    int n;
    scanf("%d", &n);
    while( n-- != 0 )
    {
        char *a, *b, *p;
        a = malloc(131072 * sizeof(*a));
        b = malloc(131072 * sizeof(*b));
        scanf("%s", a);
        scanf("%s", b);
        p = build_palindrome(a, b);
        if( p == NULL )
        {
            printf("-1\n");
        }
        else
        {
            printf("%s\n", p);
        }
        free(p);
        free(a);
        free(b);
    }
    return 0;
}

{"mode":"full","isActive":false}


Post a Comment

0 Comments