# 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.

## 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.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
if p == -1:
else:
q = st[p].childs[c]
if st[p].length + 1 == st[q].length:
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())
while p != -1 and st[p].childs[c] == q:
st[p].childs[c] = clone
last = cur
return last, sz

def print_st(st):
i = 0
for s in st:
i += 1

def solve(a, b):
n = len(a)
blen = len(b)
st = [state() for x in range(2 * n)]
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:
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 {
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)
{
radius[0] = malloc(sizeof(int) * len);
radius[1] = malloc(sizeof(int) * len);
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 );
}
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);
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}