• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Friday, January 27, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

Build a Palindrome – HackerRank Solution

Build a Palindrome - HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

bhautik bhalala by bhautik bhalala
May 24, 2022
Reading Time: 7 mins read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

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
  • Java Build a Palindrome HackerRank Solution
  • Python 3 Build a Palindrome HackerRank Solution
  • Python 2 Build a Palindrome HackerRank Solution
  • C Build a Palindrome HackerRank Solution
    • Leave a comment below
      • Related posts:

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


Copy Code Copied Use a different Browser

#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

Copy Code Copied Use a different Browser


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


Copy Code Copied Use a different Browser

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


Copy Code Copied Use a different Browser

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


Copy Code Copied Use a different Browser

#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;
}

Leave a comment below

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionBuild a String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionInsertion Sort Advanced Analysis – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMorgan and a String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAshton and String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionFind Strings – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMaking Candies – HackerRank Solution
Tags: Build a PalindromeCfull solutionHackerRank Solutionjavajava 8Python 2python 3
ShareTweetPin
bhautik bhalala

bhautik bhalala

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
29

Exclusive Time of Functions - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

Build a String - HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Gridland Provinces - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionBuild a String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionInsertion Sort Advanced Analysis – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMorgan and a String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionAshton and String – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionFind Strings – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMaking Candies – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
Shark Tank
Business

Bundil Net Worth 2022 – What Happened After Shark Tank? Everything You need to know.

September 4, 2022
0
Pro-Heroes
Anime

8 smartest Pro Heroes ranked in My Hero Academia

May 14, 2022
7
Kingdom Chapter 719 Reddit, Release Date, Countdown.
Anime

Kingdom Chapter 719 Reddit, Release Date, Countdown.

May 5, 2022
138
15 Days to learn SQL Hard SQL(Advanced)-Solution
Algorithms

Savita And Friends – HackerRank Solution

May 26, 2022
64

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?