Table of Contents
Build a Palindrome – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Build a Palindrome HackerRank Solution
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>
#include <ctime>
#include <map>
#include <math.h>
#include <cstdio>
#include <set>
#include <deque>
#include <memory.h>
#include <queue>
#pragma comment(linker, "/STACK:64000000")
typedef long long ll;
using namespace std;
const int MAXN = 1 << 18;
const int MOD = 1; // 1000 * 1000 * 1000 + 7;
const int INF = (int)(1e9);
const int SIGMA = 26;
struct state {
int len, link;
int nxt[SIGMA];
};
state st[MAXN * 2];
int sz, last;
void init() {
sz = last = 0;
st[0].len = 0;
st[0].link = -1;
++sz;
for (int i = 0; i < MAXN * 2; ++i) {
memset(st[i].nxt, -1, sizeof(st[i].nxt));
}
}
void add(char c) {
int cur = sz++;
st[cur].len = st[last].len + 1;
int p;
for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link) st[p].nxt[c] = cur;
if (p == -1) {
st[cur].link = 0;
}
else {
int q = st[p].nxt[c];
if (st[p].len + 1 == st[q].len) {
st[cur].link = q;
}
else {
int clone = sz++;
st[clone].len = st[p].len + 1;
memcpy(st[clone].nxt, st[q].nxt, sizeof(st[clone].nxt));
st[clone].link = st[q].link;
for (; p != -1 && st[p].nxt[c] == q; p = st[p].link) st[p].nxt[c] = clone;
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
int main() {
#ifdef _MSC_VER
freopen("input.txt", "r", stdin);
#endif
int T;
cin >> T;
while (T--) {
string a, b;
cin >> a >> b;
int ansLen = 0;
string ansS;
for (int it = 0; it < 2; it++) {
int n = a.length();
int m = b.length();
init();
for (int i = 0; i < m; i++) {
add(b[i] - 'a');
}
vector<int> mx(n, 0);
int l = n;
int cur = 0, len = 0;
for (int r = n - 1; r >= 0; r--) {
l = min(l, r);
while (l >= 0 && st[cur].nxt[a[l] - 'a'] != -1) {
cur = st[cur].nxt[a[l] - 'a'];
len++;
l--;
}
mx[r] = len;
len = max(len - 1, 0);
if (cur != 0 && len == st[st[cur].link].len) {
cur = st[cur].link;
}
}
vector<int> d1(n);
l = 0;
int r = -1;
for (int i = 0; i < n; i++) {
int k;
if (i > r) k = 1;
else k = min(d1[l + r - i], r - i);
while (0 <= i - k && i + k < n && a[i - k] == a[i + k]) k++;
d1[i] = k;
if (i + k - 1 > r)
r = i + k - 1, l = i - k + 1;
}
vector<int> d2(n);
l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k;
if (i > r) k = 0;
else k = min(d2[l + r - i + 1], r - i + 1);
while (i + k < n && i - k - 1 >= 0 && a[i + k] == a[i - k - 1]) k++;
d2[i] = k;
if (i + k - 1 > r)
l = i - k, r = i + k - 1;
}
d2.push_back(0);
// WHAT THE FUCK WHY AM I SHOULD DO THAT
for (int i = 0; i < n; i++) {
if (i - d1[i] + 1 == 0) d1[i]--;
if (i - d2[i] + 1 == 0) d2[i]--;
}
for (int i = 0; i < n; i++) {
int cans = d1[i] * 2 - 1;
int l = i - d1[i] + 1;
if (l > 0) cans += 2 * mx[l - 1];
if (l > 0 && mx[l - 1] && cans >= ansLen) {
ansLen = cans;
}
}
for (int i = 0; i <= n; i++) {
int cans = d2[i] * 2;
int l = i - d2[i];
if (l > 0) cans += 2 * mx[l - 1];
if (l > 0 && mx[l - 1] && cans >= ansLen) {
ansLen = cans;
}
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
swap(a, b);
}
for (int it = 0; it < 2; it++) {
int n = a.length();
int m = b.length();
init();
for (int i = 0; i < m; i++) {
add(b[i] - 'a');
}
vector<int> mx(n, 0);
int l = n;
int cur = 0, len = 0;
for (int r = n - 1; r >= 0; r--) {
l = min(l, r);
while (l >= 0 && st[cur].nxt[a[l] - 'a'] != -1) {
cur = st[cur].nxt[a[l] - 'a'];
len++;
l--;
}
mx[r] = len;
len = max(len - 1, 0);
if (cur != 0 && len == st[st[cur].link].len) {
cur = st[cur].link;
}
}
vector<int> d1(n);
l = 0;
int r = -1;
for (int i = 0; i < n; i++) {
int k;
if (i > r) k = 1;
else k = min(d1[l + r - i], r - i);
while (0 <= i - k && i + k < n && a[i - k] == a[i + k]) k++;
d1[i] = k;
if (i + k - 1 > r)
r = i + k - 1, l = i - k + 1;
}
vector<int> d2(n);
l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k;
if (i > r) k = 0;
else k = min(d2[l + r - i + 1], r - i + 1);
while (i + k < n && i - k - 1 >= 0 && a[i + k] == a[i - k - 1]) k++;
d2[i] = k;
if (i + k - 1 > r)
l = i - k, r = i + k - 1;
}
d2.push_back(0);
// WHAT THE FUCK WHY AM I SHOULD DO THAT
for (int i = 0; i < n; i++) {
if (i - d1[i] + 1 == 0) d1[i]--;
if (i - d2[i] + 1 == 0) d2[i]--;
}
for (int i = 0; i < n; i++) {
int cans = d1[i] * 2 - 1;
int l = i - d1[i] + 1;
if (l > 0) cans += 2 * mx[l - 1];
if (l > 0 && mx[l - 1] && cans >= ansLen) {
int ansC = i;
string nans = "";
for (int i = ansC - d1[ansC] + 1; i <= ansC + d1[ansC] - 1; i++) nans += a[i];
string ss;
int l = ansC - d1[ansC] + 1;
if (l > 0) {
for (int i = 0; i < mx[l - 1]; i++) ss += a[l - 1 - i];
}
nans += ss;
reverse(ss.begin(), ss.end());
nans = ss + nans;
if (nans.length() > ansS.length() || nans < ansS) ansS = nans;
ansLen = ansS.length();
}
}
for (int i = 0; i <= n; i++) {
int cans = d2[i] * 2;
int l = i - d2[i];
if (l > 0) cans += 2 * mx[l - 1];
if (l > 0 && mx[l - 1] && cans >= ansLen) {
int ansC = i;
string nans = "";
for (int i = ansC - d2[ansC]; i < ansC + d2[ansC]; i++) nans += a[i];
string ss;
int l = ansC - d2[ansC];
if (l > 0) {
for (int i = 0; i < mx[l - 1]; i++) ss += a[l - 1 - i];
}
nans += ss;
reverse(ss.begin(), ss.end());
nans = ss + nans;
if (nans.length() > ansS.length() || nans < ansS) ansS = nans;
ansLen = ansS.length();
}
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
swap(a, b);
}
if (ansS == "") cout << -1 << endl;
else cout << ansS << endl;
}
return 0;
}
Java Build a Palindrome HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class F3 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
for(int T = ni();T > 0;T--){
char[] s = ns().toCharArray();
char[] t = ns().toCharArray();
String b1 = go(s, t);
// tr(best);
char[] rs = rev(s);
char[] rt = rev(t);
String b2 = go(rt, rs);
if(b1 == null && b2 == null){
out.println(-1);
}else if(b1 == null){
out.println(b2);
}else if(b2 == null){
out.println(b1);
}else if(b1.length() > b2.length() || b1.length() == b2.length() && b1.compareTo(b2) < 0){
out.println(b1);
}else{
out.println(b2);
}
}
}
public static char[] rev(char[] a)
{
for(int i = 0, j = a.length-1;i < j;i++,j--){
char c = a[i]; a[i] = a[j]; a[j] = c;
}
return a;
}
String go(char[] s, char[] t)
{
char[] st = new char[s.length+t.length];
for(int i = 0;i < s.length;i++)st[i] = s[s.length-1-i];
for(int i = 0;i < t.length;i++)st[i+s.length] = t[i];
// String S = new String(s);
// String ST = new String(st);
int[] sa = sa(st);
int nn = s.length+t.length;
int[] isa = new int[nn];
for(int i = 0;i < nn;i++)isa[sa[i]] = i;
int[] lcp = buildLCP(st, sa);
// tr(st);
// tr(sa);
int[] llcp = new int[nn];
{
int cur = 0;
for(int i = 0;i < nn;i++){
if(sa[i] < s.length){
llcp[s.length-1-sa[i]] = cur;
}else{
cur = 9999999;
}
if(i+1 < nn)cur = Math.min(cur, lcp[i+1]);
}
}
int[] rlcp = new int[nn];
{
int cur = 0;
for(int i = nn-1;i >= 0;i--){
if(sa[i] < s.length){
rlcp[s.length-1-sa[i]] = cur;
}else{
cur = 9999999;
}
cur = Math.min(cur, lcp[i]);
}
}
// tr(llcp, rlcp);
int[] rad = palindrome(s);
// tr("s", new String(s));
// tr(rad);
int[] pals = new int[s.length];
{
int[][] es = new int[s.length*2-1][];
for(int i = 0;i < s.length*2-1;i++){
es[i] = new int[]{(i-rad[i]+1)/2, rad[i]};
}
Arrays.sort(es, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
int p = 0;
int cur = 0;
for(int i = 0;i < s.length;i++){
while(p < es.length && es[p][0] <= i){
cur = Math.max(cur, es[p][1]);
p++;
}
pals[i] = Math.max(pals[i], cur);
cur = Math.max(cur-2, 0);
}
}
// tr("pals", pals);
char[] srs = new char[s.length*2];
for(int i = 0;i < s.length;i++){
srs[i] = srs[s.length*2-1-i] = s[i];
}
int[] ssa = sa(srs);
int[] issa = new int[srs.length];
for(int i = 0;i < srs.length;i++)issa[ssa[i]] = i;
int[] slcp = buildLCP(srs, ssa);
SegmentTreeRMQ sts = new SegmentTreeRMQ(slcp);
int maxlen = 0;
int[] lbest = null;
for(int start = 0;start < s.length;start++){
int xlcp = Math.min(start+1, Math.max(llcp[start], rlcp[start]));
if(xlcp == 0)continue;
int lpal = start+1 < s.length ? pals[start+1] : 0;
// tr(start, xlcp, lpal);
int len = lpal+xlcp*2;
if(len > maxlen){
maxlen = len;
lbest = new int[]{start-xlcp+1, start+lpal+1, s.length-1-start+s.length, s.length-1-(start-xlcp+1)+1+s.length};
}else if(len == maxlen){
int[] can = new int[]{start-xlcp+1, start+lpal+1, s.length-1-start+s.length, s.length-1-(start-xlcp+1)+1+s.length};
int ulcp = sts.minx(Math.min(issa[can[0]], issa[lbest[0]])+1, Math.max(issa[can[0]], issa[lbest[0]])+1);
if(ulcp < can[1]-can[0] && ulcp < lbest[1]-lbest[0]){
if(issa[can[0]] < issa[lbest[0]]){
lbest = can;
}
continue;
}
int L = can[1]-can[0];
int R = lbest[1]-lbest[0];
if(L < R){
int lpos = can[2], rpos = lbest[0]+L;
ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
if(ulcp < R-L){
if(issa[lpos] < issa[rpos]){
lbest = can;
}
continue;
}
lpos = can[2] + R-L; rpos = lbest[2];
ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
if(issa[lpos] < issa[rpos]){
lbest = can;
}
}else{
int lpos = can[0]+R, rpos = lbest[2];
ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
if(ulcp < L-R){
if(issa[lpos] < issa[rpos]){
lbest = can;
}
continue;
}
lpos = can[2]; rpos = lbest[2]+L-R;
ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
if(issa[lpos] < issa[rpos]){
lbest = can;
}
}
}
}
if(lbest == null){
return null;
}else{
StringBuilder sb = new StringBuilder();
for(int i = lbest[0];i < lbest[1];i++)sb.append(srs[i]);
for(int i = lbest[2];i < lbest[3];i++)sb.append(srs[i]);
return sb.toString();
}
}
public static class SegmentTreeRMQ {
public int M, H, N;
public int[] st;
public SegmentTreeRMQ(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
Arrays.fill(st, 0, M, Integer.MAX_VALUE);
}
public SegmentTreeRMQ(int[] a)
{
N = a.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
for(int i = 0;i < N;i++){
st[H+i] = a[i];
}
Arrays.fill(st, H+N, M, Integer.MAX_VALUE);
for(int i = H-1;i >= 1;i--)propagate(i);
}
public void update(int pos, int x)
{
st[H+pos] = x;
for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
}
private void propagate(int i)
{
st[i] = Math.min(st[2*i], st[2*i+1]);
}
public int minx(int l, int r){
if(l >= r)return 0;
int min = Integer.MAX_VALUE;
while(l != 0){
int f = l&-l;
if(l+f > r)break;
int v = st[(H+l)/f];
if(v < min)min = v;
l += f;
}
while(l < r){
int f = r&-r;
int v = st[(H+r)/f-1];
if(v < min)min = v;
r -= f;
}
return min;
}
public int min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
private int min(int l, int r, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return st[cur];
}else{
int mid = cl+cr>>>1;
int ret = Integer.MAX_VALUE;
if(cl < r && l < mid){
ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
}
if(mid < r && l < cr){
ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
}
return ret;
}
}
public int firstle(int l, int v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur;
}else{
return cur-H;
}
}else{
cur++;
if((cur&cur-1) == 0)return -1;
if((cur&1)==0)cur>>>=1;
}
}
}
public int lastle(int l, int v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur+1;
}else{
return cur-H;
}
}else{
if((cur&cur-1) == 0)return -1;
cur--;
if((cur&1)==1)cur>>>=1;
}
}
}
}
public static int[] palindrome(char[] str)
{
int n = str.length;
int[] r = new int[2*n];
int k = 0;
for(int i = 0, j = 0;i < 2*n;i += k, j = Math.max(j-k, 0)){
// normally
while(i-j >= 0 && i+j+1 < 2*n && str[(i-j)/2] == str[(i+j+1)/2])j++;
r[i] = j;
// skip based on the theorem
for(k = 1;i-k >= 0 && r[i]-k >= 0 && r[i-k] != r[i]-k;k++){
r[i+k] = Math.min(r[i-k], r[i]-k);
}
}
return r;
}
private static interface BaseArray {
public int get(int i);
public void set(int i, int val);
public int update(int i, int val);
}
private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;
CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}
public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}
public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}
private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;
IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i];
}
public void set(int i, int val) {
m_A[m_pos + i] = val;
}
public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}
/* find the start or end of each bucket */
private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}
private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}
/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}
private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;
/*
* compact all the sorted substrings into the first m items of SA 2*m
* must be not larger than n (proveable)
*/
for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}
/* store the length of all substrings */
i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
/* find the lexicographic names of all substrings */
for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}
return name;
}
/* compute SA and BWT */
private static void induceSA(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}
/*
* find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
* (excluding T and SA) of at most 2n+O(1) for a constant alphabet
*/
private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;
if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}
/*
* stage 1: reduce the problem by at least 1/2 sort all the
* LMS-substrings
*/
getCounts(T, C, n, k);
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}
/*
* stage 2: solve the reduced problem recurse if names are not yet
* unique
*/
if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;
i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}
/* stage 3: induce the result for the original problem */
if((flags & 8) != 0){
getCounts(T, C, n, k);
}
/* put all left-most S characters into their buckets */
if(1 < m){
getBuckets(C, B, k, true); /* find ends of buckets */
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}
/* char */
public static void suffixsort(char[] T, int[] SA, int n) {
if((T == null) || (SA == null) || (T.length < n) || (SA.length < n)){
return;
}
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 128);
}
public static int[] sa(char[] T)
{
int n = T.length;
int[] sa = new int[n];
suffixsort(T, sa, n);
return sa;
}
public static int[] buildLCP(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] isa = new int[n];
for(int i = 0;i < n;i++)isa[sa[i]] = i;
for(int i = 0;i < n;i++){
if(isa[i] > 0){
for(int j = sa[isa[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
lcp[isa[i]] = h;
}else{
lcp[isa[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new F3().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Build a Palindrome HackerRank Solution
from os.path import basename,exists,expanduser,splitext,isfile
from os import getcwd
from sys import stdin,modules,path
import sys
from array import array as ar
from collections import Counter,defaultdict as ddict
from functools import reduce as red
from math import sqrt,log
import itertools as it
from itertools import accumulate as acc,permutations as per,dropwhile as dpw,takewhile as tkw,combinations as cmbs
from itertools import groupby,product
from copy import deepcopy
from random import randint,shuffle as shuf,sample
import re
lolPath=getcwd()
randid="\qosdjfoiz.txt"
home=isfile(lolPath+randid)
## reponse pour 01:122
def inv(n):return pow(n,modo-2,modo)
## creer un version raccourcie d'une chaine ou d'une séquence
def shrt(strn):return strn if len(strn)<101 else strn[:38]+('....' if type(strn).__name__=='str' else [None,None,None])+strn[-38:]
def setCstes(traceVal=0):
global trace
trace=traceVal
if home:
filbase=splitext((__file__))[0].split('_')[0]
from mesures import ch
else:filou=None
modo=10**9+7
mxszDico=6
mxProfArbre=6
from random import random
## générer une chaine aléatoire de taille donnée et liste de caractères de taille à à 26
def gench(sz,cset=26):
return ''.join('abcdefghijklmnopqrstuvwxyz'[randint(0,cset-1)] for _ in range(sz))
## genérer un dictionaire des sous chaines d'un chaine pour une taille de chaine donnée
def gendpsz(a):
sa=[set(a[ix:ix+sz] for ix in range(1,len(a)-sz-1))for sz in range(1,mxszDico)]
da=ddict(lambda :[])
for ix in range(len(a)-mxszDico-1):da[a[ix:ix+mxszDico]]+=[ix]
return sa+[da]
def monochar(a,b):
c=a[0]
for ix in range(1,len(a)):
if a[ix]!=c:return None
fnd=re.findall(c+c+'*',b)
if fnd:return a+max(fnd)
else:return '-1'
## générer un arbre des sous-chaînes jusqu'à une taille donnée.
## cet arbre utilise des dictionnaires en cascade.
## sauf au niveau le plus bas qui contient une liste
def arbreChaines(s):
racine={}
pri=''
for ix in range(len(s)):
cd=racine
try:
for c in s[ix:ix+mxProfArbre]:
if c not in cd:cd[c]={}
cdp,cp=cd,c
cd=cd[c]
cd[s[ix+mxProfArbre]]=cd.get(s[ix+mxProfArbre],[])+[ix]
except IndexError:
if len(cd)==0 :cdp[cp]=[ix]
pri=s[ix]
return racine
def souf2(A,b,arb,ixa,pal) :
global fnd,mieux
off='\t\t\t\t'
if trace&2:print(off+"souf2 ixa {} lenpal {} pal {}".format(ixa,len(pal),pal))
sz=0
dc=arb
while type(dc).__name__=='dict' and ixa+sz<len(A) and A[ixa+sz] in dc:dc,sz=dc[A[ixa+sz]],sz+1
## soit on a epuisé la profondeur du dictionnaire, soit on a un caractère
## qui ne matche pas,soit on a épuisé A
if trace&8:print(off+"sz {} dc {}".format(sz,type(dc).__name__))
if sz==0:return
if type(dc).__name__=='dict':
if 2*sz+len(pal)<len(fnd):return ## abandonner si on ne va pas battre le record
if ixa+sz==len(A):chn=A[ixa:ixa+sz]
else:chn=A[ixa:ixa+sz] ## ça peut être 0 si le premier caractère dans A n'est pas du tout dans b
elif sz<mxProfArbre:chn=A[ixa:ixa+sz] ## on ne se fatigue pas à trouver un palindrome intercalaire, on le trouvera ## quand on fera les recherches depuis b
elif sz==mxProfArbre: ## si on a atteint le fond de l'arbre, on continue d'explorer à la main
szm=sz
for ixb in dc: ## on peut avoir plusieurs corresps dans b, il faut les explorer toutes
szt=sz
while ixa+szt<len(A) and ixb+szt<len(b) and A[ixa+szt]==b[ixb+szt]:szt+=1
if szt>szm:szm,ixbm=szt,ixb
chn=A[ixa:ixa+szm]
else:
bas,haut,ixbBas=mieux
if ixa>=bas and ixa<haut:szm,ixbm=haut-ixa,ixbBas+ixa-bas
else: szm,ixbm=sz,None
for ixb in dc: ## on peut avoir plusieurs corresps dans b, il faut les explorer toutes
if ixb==ixbm:continue
szt=sz
while ixa+szt<len(A) and ixb+szt<len(b) and A[ixa+szt]==b[ixb+szt]:szt+=1
if szt>=szm:szm,ixbm=szt,ixb
mieux=[ixa,ixa+szm,ixbm]
if 2*szm+len(pal)<len(fnd):return
chn=A[ixa:ixa+szm]
cho=chn
chn=''.join(reversed(chn))+pal+chn
if len(chn)>len(fnd) or (len(chn)==len(fnd) and chn<fnd): fnd=chn
return
## balayer A inversé. A chaque position, on essaie chaque taille
## de palindrome local, à partir de la taille un, et on cherche
## la chaine maximale qui le suit et qui est dans b
## Pour la position 0, c'est le seul cas où on essaie un palindrome
## de taille nulle
def souf1(A,b,arb) :
global fnd
ixA,pal=0,''
souf2(A,b,arb,ixA,pal)
## pour chaque position, trouver tous les palindromes qui l'entourent
for ixA in range(len(A)):
peutPair,peutImpair=True,True
for szp in range(1,2*ixA+2):
try:
if szp&1 and peutImpair: ## taille impaire
dl=(szp>>1)
if ixA-dl<0 or ixA+dl>=len(A) or A[ixA-dl]!=A[ixA+dl]:
peutImpair=False ## pas un palindrome, fin de la recherche Impairs
if not peutPair:break
else:
pal=A[ixA-dl:ixA+dl+1]
souf2(A,b,arb,ixA+dl+1,pal)
elif peutPair: ## taille paire
dl=(szp>>1)
if ixA-dl<0 or ixA+dl-1>=len(A) or A[ixA-dl]!=A[ixA+dl-1]:
peutPair=False
if not peutImpair:break
else:
pal=A[ixA-dl:ixA+dl]
souf2(A,b,arb,ixA+dl,pal)
except IndexError:
print("IndexError",ixA,dl,peutPair,peutImpair,len(A),len(b))
exit(1)
def faire(a,b):
global fnd,mieux
mieux=[0,0,0]
fnd=chr(127)
m=monochar(a,b)
if m:return m
m=monochar(b,a)
if m:return m
A=''.join(reversed(a))
arA=arbreChaines(A)
arb=arbreChaines(b)
souf1(A,b,arb)
souf1(b,A,arA)
return fnd if fnd!=chr(127) else '-1'
trace=0
if modules[__name__].__name__=='__main__':
if home:
prv=0
cr=ch()
print("lecture ")
lif=[open(filbase+'In'+filn+'.txt') for filn in ('24','13')]
else:
trace=0
lif=[stdin]
for rd in lif:
try:
if home:print(rd.name)
for _ in range(int(rd.readline().strip())):
a,b=rd.readline().strip(),rd.readline().strip()
if home:
print(len(a),shrt(a),len(b),shrt(b))
for f in faire,:
cr=ch()
res=f(a,b)
print("\t",f.__name__,shrt(res),cr.lap())
else:print(faire(a,b))
except EOFError :pass
except ValueError:pass
Python 2 Build a Palindrome HackerRank Solution
def build_palindrome_lookup(s):
sx = '|'+'|'.join(s)+'|'
sxlen = len(sx)
rslt = [ 0 ] * sxlen
c=0;r=0;m=0;n=0
for i in xrange(1,sxlen):
#print i, rslt
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)
#print rslt
for i in xrange(1,sxlen-1):
idx = (i-rslt[i])/2
res[idx] = max(res[idx], rslt[i])
#print 'res: ',res
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 xrange(2*n) ]
st[0].link=-1;st[0].length=0
last = 0; sz = 1
last, sz = build_part_st(a,st, 1, last, sz)
#print_st(st)
plookup = build_palindrome_lookup(b)
apos = 0; start = -1 ; left=0;mid=0;total=0;curlen=0
for i in xrange(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 xrange(left+mid):
palindrome.append(b[start+i])
for i in xrange(left-1,-1,-1):
palindrome.append(palindrome[i])
return ''.join(palindrome)
def lex_gt(s, old_start, new_start, size):
for i in xrange(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)
#print rslt1, rslt2
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 xrange(input()):
a = raw_input()
b = raw_input()
print process_helper(a,b)
C Build a Palindrome HackerRank Solution
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.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;
/* Sort and merge palindrome intervals */
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;
}
/* Convert intervals into result format */
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;
}
/* Calculate array A, where A[i] is euqal to length of longest possible
palindrome substring of s, that begins from i-position. O(n * log(n))
*/
int* find_longest_palindromes(const char *s, int len)
{
int *result;
int *radius[2]; /* matrix with palindrome radius for even and odd length palindromes */
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;
int 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;
}
/* longest common prefix array, O(n) */
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; /* suffix number */
int bucket[2]; /* sorted position of first and second H symbols */
};
/* Suffix array calculation. O(n * log(n)) */
int * SA(const char *s, int len)
{
/* positions of already sorted suffixes */
int *p = malloc(sizeof(int) * len);
/* result suffix array */
int *sa = malloc(sizeof(int) * len);
/* state for radix sort and temporary buffer for radix sort */
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; /* suffix number */
state[i].bucket[0] = p[i]; /* sorted position of first H symbols */
if (i + h < len) {
state[i].bucket[1] = p[i + h];
} else {
state[i].bucket[1] = 0;
}
}
/* radix sort state array */
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];
}
/* store radix sort result into temporary array */
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 *);
}
}
/* Write calculated index into p */
for (int i = 0, bucket = 0; i < len; ++i) {
if ((h << 1) >= len || /* Do not group the bucket if we produce result aray*/
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);
int blen = strlen(b);
int *sa, *lcp, *p, *lcp_ab;
int maxlen = 0;
int suffix = -1;
char *result = NULL;
/* build string <a>$<reversed b> */
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';
/* calculate suffix array and LCP array */
sa = SA(s, slen);
lcp = LCP(s, slen, sa);
/* calculate LCP between A and B substings */
lcp_ab = calloc(slen, sizeof(*lcp_ab));
{
int i = 1;
while (i < slen - 1) {
/* if current LCP[i] is a non-zero common lenght between A and B substrings */
if (lcp[i] && ((sa[i] > alen && sa[i + 1] < alen) || (sa[i] < alen && sa[i + 1] > alen))) {
int j;
int 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]);
}
assert(j - 2 >= i);
i = j - 1;
} else {
++i;
}
}
}
/* calculate longest palindromes array */
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;
}
