Hello Programmers, In this post, you will learn how to solve HackerRank Build a Palindrome Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t straight away look for the solutions, first try to solve the problems by yourself. If you find any difficulty after trying several times, then look for the solutions. We are going to solve the HackerRank Algorithms problems using C, CPP, JAVA, PYTHON, JavaScript & SCALA Programming Languages.

HackerRank Build a Palindrome Solution
Task
You have two strings, a and b. Find a string, s, such that:
- s can be expressed as s = sa + sb where sa is a non–empty substring of a and sb is a non-empty substring of b.
- s is a palindromic string.
- The length of s is as long as possible.
For each of the q pairs of strings (ai and bi) received as input, find and print string si on a new line. If you’re able to form more than one valid string si, print whichever one comes first alphabetically. If there is no valid answer, print -1 instead.
Input Format
The first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query over two lines:
- The first line contains a single string denoting a.
- The second line contains a single string denoting b.
Constraints
- 1 <= q <= 10
- 1 <= |a|, |b| <= 105
- a and b contain only lowercase English letters.
- Sum of |a| over all queries does not exceed 2 x 105
- Sum of |b| over all queries does not exceed 2 x 105
Output Format
For each pair of strings (ai and bi), find some si satisfying the conditions above and print it on a new line. If there is no such string, print -1 instead.
Sample Input
3
bac
bac
abc
def
jdfh
fds
Sample Output
aba
–1
dfhfd
Explanation
We perform the following three queries:
- Concatenate sa = “a” with sb = “ba” to create s = “aba”.
- We’re given a = “abc” and sa = “def”; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print –1.
- Concatenate sa = “dfh” with sb = “fd” to create s = “dfhfd”. Note that we chose these particular substrings because the length of string s must be maximal.
HackerRank Build a Palindrome Solution
HackerRank Build a Palindrome Solution in C
#include <stdio.h> #include <stdlib.h> #include <string.h> #define A_SIZE 26 #define MIN_C 'a' typedef struct _st_node st_node; typedef struct _st_edge st_edge; typedef enum _type{ ONE=1, TWO, BOTH } type; struct _st_node{ st_node *suffix_link; type t; st_edge *edges[A_SIZE+2]; }; struct _st_edge{ int from; int to; int suffix_index; st_node *node; }; typedef struct _pt_node{ int len; struct _pt_node *suffix_link; struct _pt_node *edges[A_SIZE]; } pt_node; void dfs(st_node *root,int suffix_idx,int len,int flag); void suffix_tree(st_node *root,char *str,int len,int flag,int offset); void generalized_suffix_tree(st_node *root,char *str,int len1,int len2); void palindromic_tree(pt_node *root1,pt_node *root2,char *str,int len,int *p_len); char a[200001],b[100001],c[100001],ans[200001]; int a_len[100000],b_len[100000],max_len,lena,lenb; int main(){ int q,i; st_node root; pt_node r1,r2; scanf("%d",&q); while(q--){ scanf("%s%s",a,b); lena=strlen(a); lenb=strlen(b); for(i=0;i<lena;i++) c[lena-i-1]=a[i]; c[lena]=0; palindromic_tree(&r1,&r2,c,lena,a_len); palindromic_tree(&r1,&r2,b,lenb,b_len); for(i=0;i<lena/2;i++){ a_len[i]^=a_len[lena-i-1]; a_len[lena-i-1]^=a_len[i]; a_len[i]^=a_len[lena-i-1]; } for(i=0;i<lenb/2;i++){ b_len[i]^=b_len[lenb-i-1]; b_len[lenb-i-1]^=b_len[i]; b_len[i]^=b_len[lenb-i-1]; b[i]^=b[lenb-i-1]; b[lenb-i-1]^=b[i]; b[i]^=b[lenb-i-1]; } strcat(a,b); generalized_suffix_tree(&root,a,lena,lenb); max_len=0; dfs(&root,0,0,0); if(max_len){ for(i=0;i<max_len;i++) printf("%c",ans[i]); printf("\n"); } else printf("-1\n"); } return 0; } void dfs(st_node *root,int suffix_idx,int len,int flag){ int i,j,k; if(!root){ if(len) if(!flag){ if(suffix_idx+len==lena) k=0; else k=a_len[suffix_idx+len]; if(len*2+k>max_len){ max_len=len*2+k; for(i=suffix_idx,j=0;i<suffix_idx+len;i++) ans[j++]=a[i]; for(i=suffix_idx+len;i<suffix_idx+len+k;i++) ans[j++]=a[i]; for(i=suffix_idx+len-1;i>=suffix_idx;i--) ans[j++]=a[i]; } } else{ if(suffix_idx+len-lena==lenb) k=0; else k=b_len[suffix_idx+len-lena]; if(len*2+k>max_len){ max_len=len*2+k; for(i=suffix_idx,j=0;i<suffix_idx+len;i++) ans[j++]=a[i]; for(i=suffix_idx+len-lena;i<suffix_idx+len-lena+k;i++) ans[j++]=b[i]; for(i=suffix_idx+len-1;i>=suffix_idx;i--) ans[j++]=a[i]; } } return; } if(root->edges[A_SIZE]) dfs(root->edges[A_SIZE]->node,root->edges[A_SIZE]->suffix_index,len,0); if(root->edges[A_SIZE+1]) dfs(root->edges[A_SIZE+1]->node,root->edges[A_SIZE+1]->suffix_index,len,1); for(i=0;i<A_SIZE;i++) if(root->edges[i]) if(root->edges[i]->node->t==BOTH) dfs(root->edges[i]->node,root->edges[i]->suffix_index,len+root->edges[i]->to-root->edges[i]->from+1,flag); else if(root->edges[i]->node->t==ONE) dfs(root->edges[i]->node,root->edges[i]->suffix_index,len,0); else dfs(root->edges[i]->node,root->edges[i]->suffix_index,len,1); return; } void suffix_tree(st_node *root,char *str,int len,int flag,int offset){ int a_edge,a_len=0,remainder=0,need_insert,from,max,i; type t; st_node *a_node=root,*pre_node,*t_node,*tt_node,*pp_node=NULL; st_edge *t_edge; if(flag){ max=A_SIZE+1; t=TWO; } else{ max=A_SIZE; t=ONE; } root->t|=t; for(i=offset;i<=offset+len;i++){ need_insert=0; pre_node=NULL; remainder++; if(i==offset+len) need_insert=1; else if(a_len) if(str[a_node->edges[a_edge]->from+a_len]==str[i]) if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){ a_node=a_node->edges[a_edge]->node; a_node->t|=t; a_len=0; } else a_len++; else need_insert=1; else if(a_node->edges[str[i]-MIN_C]) if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to){ a_node=a_node->edges[str[i]-MIN_C]->node; a_node->t|=t; } else{ a_edge=str[i]-MIN_C; a_len=1; } else need_insert=1; if(need_insert) for(;remainder>0;remainder--){ if(!a_len) if(i==offset+len){ a_node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); a_node->edges[max]->suffix_index=i-remainder+1; a_node->edges[max]->node=NULL; t_node=tt_node=a_node; } else{ if(a_node->edges[str[i]-MIN_C]){ if(pre_node) pre_node->suffix_link=a_node; if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to){ a_node=a_node->edges[str[i]-MIN_C]->node; a_node->t|=t; } else{ a_edge=str[i]-MIN_C; a_len=1; } break; } t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=i; t_edge->to=offset+len-1; t_edge->suffix_index=i-remainder+1; t_edge->node=(st_node*)malloc(sizeof(st_node)); memset(t_edge->node,0,sizeof(st_node)); t_edge->node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_edge->node->edges[max]->suffix_index=i-remainder+1; t_edge->node->edges[max]->node=NULL; t_edge->node->t|=t; a_node->edges[str[i]-MIN_C]=t_edge; t_node=a_node; tt_node=t_edge->node; } else{ if(i!=offset+len && str[a_node->edges[a_edge]->from+a_len]==str[i]){ if(pre_node) pre_node->suffix_link=a_node; if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){ a_node=a_node->edges[a_edge]->node; a_node->t|=t; a_len=0; } else a_len++; break; } t_node=(st_node*)malloc(sizeof(st_node)); memset(t_node,0,sizeof(st_node)); t_node->t|=(a_node->edges[a_edge]->node->t|t); t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=a_node->edges[a_edge]->from+a_len; t_edge->to=a_node->edges[a_edge]->to; t_edge->suffix_index=a_node->edges[a_edge]->suffix_index; t_edge->node=a_node->edges[a_edge]->node; from=a_node->edges[a_edge]->from; a_node->edges[a_edge]->node=t_node; a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1; t_node->edges[str[t_edge->from]-MIN_C]=t_edge; if(i==offset+len){ t_node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_node->edges[max]->suffix_index=i-remainder+1; t_node->edges[max]->node=NULL; tt_node=t_node; } else{ t_edge=(st_edge*)malloc(sizeof(st_edge)); t_edge->from=i; t_edge->to=offset+len-1; t_edge->suffix_index=i-remainder+1; t_edge->node=(st_node*)malloc(sizeof(st_node)); memset(t_edge->node,0,sizeof(st_node)); t_edge->node->edges[max]=(st_edge*)malloc(sizeof(st_edge)); t_edge->node->edges[max]->suffix_index=i-remainder+1; t_edge->node->edges[max]->node=NULL; t_edge->node->t|=t; t_node->edges[str[i]-MIN_C]=t_edge; tt_node=t_edge->node; } } if(pre_node) pre_node->suffix_link=t_node; pre_node=t_node; if(pp_node) pp_node->suffix_link=tt_node; pp_node=tt_node; if(a_node==root && a_len>0){ if(remainder>1) a_edge=str[i-remainder+2]-MIN_C; from=i-remainder+2; a_len--; } else if(a_node!=root) if(a_node->suffix_link){ a_node=a_node->suffix_link; a_node->t|=t; } else a_node=root; while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){ a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1; from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1; a_node=a_node->edges[a_edge]->node; a_node->t|=t; a_edge=str[from]-MIN_C; } } } return; } void generalized_suffix_tree(st_node *root,char *str,int len1,int len2){ memset(root,0,sizeof(st_node)); suffix_tree(root,str,len1,0,0); suffix_tree(root,str,len2,1,len1); return; } void palindromic_tree(pt_node *root1,pt_node *root2,char *str,int len,int *p_len){ int i; pt_node *pre,*p,*largest; memset(root1,0,sizeof(pt_node)); memset(root2,0,sizeof(pt_node)); root1->len=-1; root2->len=0; root2->suffix_link=root1; for(largest=root2,i=0;i<len;i++){ for(p=largest,pre=largest=NULL;p;p=p->suffix_link) if(i-p->len-1>=0 && str[i-p->len-1]==str[i]) if(p->edges[str[i]-MIN_C]){ if(!largest){ largest=p->edges[str[i]-MIN_C]; p_len[i]=largest->len; } if(pre) pre->suffix_link=p->edges[str[i]-MIN_C]; break; } else{ p->edges[str[i]-MIN_C]=(pt_node*)malloc(sizeof(pt_node)); memset(p->edges[str[i]-MIN_C],0,sizeof(pt_node)); p->edges[str[i]-MIN_C]->len=p->len+2; if(!largest){ largest=p->edges[str[i]-MIN_C]; p_len[i]=largest->len; } if(pre) pre->suffix_link=p->edges[str[i]-MIN_C]; pre=p->edges[str[i]-MIN_C]; } if(pre && !pre->suffix_link) pre->suffix_link=root2; } return; }
HackerRank Build a Palindrome Solution in Cpp
#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; }
HackerRank Build a Palindrome Solution in Java
import java.util.*; public class PalindromeBuilder { public static class State { int length; int link; int[] next = new int[128]; int endpos; final List<Integer> ilink; public State() { Arrays.fill(next, -1); ilink = new ArrayList<>(); } } public static State[] buildSuffixAutomaton(String s) { int n = s.length(); State[] st = new State[Math.max(2, 2 * n - 1)]; st[0] = new State(); st[0].link = -1; st[0].endpos = -1; int last = 0; int size = 1; for (char c : s.toCharArray()) { int cur = size++; st[cur] = new State(); st[cur].length = st[last].length + 1; st[cur].endpos = st[last].length; int p = go(st, last, -1, c, cur); if (p == -1) { st[cur].link = 0; } else { int q = st[p].next[c]; if (st[p].length + 1 == st[q].length) st[cur].link = q; else { int clone = size++; st[clone] = new State(); st[clone].length = st[p].length + 1; st[clone].next = st[q].next.clone(); st[clone].link = st[q].link; go(st, p, q, c, clone); st[q].link = clone; st[cur].link = clone; st[clone].endpos = -1; } } last = cur; } for (int i = 1; i < size; i++) { st[st[i].link].ilink.add(i); } return Arrays.copyOf(st, size); } private static int go(State[] st, int p, int q, char c, int ns) { while (p != -1 && st[p].next[c] == q) { st[p].next[c] = ns; p = st[p].link; } return p; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; ++i) { String a = sc.next(); String b = sc.next(); System.out.println(solve(a, b)); } } static String candidate(String a, String b) { State[] as = buildSuffixAutomaton(a); int[] l = buildPalindromeLookup(b); int len = 0; int bestHalf = 0; int bestMid = 0; int bestTotal = 0; int start = -1; for (int i = 0, aPos = 0; i < b.length(); ++i) { char c = b.charAt(i); if (as[aPos].next[c] == -1) { while (aPos != -1 && as[aPos].next[c] == -1) { aPos = as[aPos].link; } if (aPos == -1) { aPos = 0; len = 0; continue; } len = as[aPos].length; } ++len; aPos = as[aPos].next[c]; int nStart = i - len + 1; int nMid = 0; if (i + 1 < b.length()) { nMid = l[i + 1]; } int nTotal = 2*len + nMid; if (bestTotal < nTotal || (bestTotal == nTotal && gt(b, start, nStart, len + nMid))) { bestHalf = len; bestMid = nMid; bestTotal = nTotal; start = nStart; } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < bestHalf + bestMid; ++i) { sb.append(b.charAt(start + i)); } for (int i = bestHalf - 1; i >= 0; --i) { sb.append(sb.charAt(i)); } return sb.toString(); } static String solve(String a, String b) { String rb = rev(b); String res = candidate(a, rb); String c1 = candidate(rb, a); if (c1.length() > res.length() || (c1.length() == res.length() && c1.compareTo(res) < 0)) { res = c1; } if (res.length() == 0) { res = "-1"; } return res; } static String rev(String s) { StringBuilder sb = new StringBuilder(); for (int i = s.length() - 1; i >= 0; --i) { sb.append(s.charAt(i)); } return sb.toString(); } static boolean gt(String s, int start, int nStart, int size) { int cmp = 0; for (int i = 0; i < size; ++i) { cmp = Character.compare(s.charAt(start + i), s.charAt(nStart + i)); if (cmp != 0) { break; } } return cmp > 0; } static int[] buildPalindromeLookup(String s) { char[] s2 = addBoundaries(s.toCharArray()); int[] p = new int[s2.length]; int c = 0, r = 0; int m = 0, n = 0; for (int i = 1; i < s2.length; i++) { if (i > r) { p[i] = 0; m = i - 1; n = i + 1; } else { int i2 = c * 2 - i; if (p[i2] < (r-i)) { p[i] = p[i2]; m = -1; } else { p[i] = r - i; n = r + 1; m = i * 2 - n; } } while (m >= 0 && n < s2.length && s2[m] == s2[n]) { p[i]++; m--; n++; } if ((i + p[i]) > r) { c = i; r = i + p[i]; } } int[] res = new int[s.length()]; for (int i = 1; i < s2.length - 1; i++) { int idx = (i - p[i])/2; res[idx] = Math.max(res[idx], p[i]); } return res; } private static char[] addBoundaries(char[] cs) { if (cs == null || cs.length == 0) return "||".toCharArray(); char[] cs2 = new char[cs.length * 2 + 1]; for (int i = 0; i < cs2.length - 1; i += 2) { cs2[i] = '|'; cs2[i + 1] = cs[i / 2]; } cs2[cs2.length - 1] = '|'; return cs2; } }
HackerRank Build a Palindrome Solution in Python
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)
HackerRank Build a Palindrome Solution using JavaScript
"use strict"; const fs = require("fs"); process.stdin.resume(); process.stdin.setEncoding("utf-8"); let inputString = ""; let currentLine = 0; process.stdin.on("data", inputStdin => { inputString += inputStdin; }); process.stdin.on("end", _ => { inputString = inputString .trim() .split("\n") .map(str => str.trim()); main(); }); function readLine() { return inputString[currentLine++]; } /* * Complete the buildPalindrome function below. */ // Object to save status of each characters function State() { let link = -1; let posStart = 0; let childs = {}; return { link, posStart, childs }; } // reverse the string function reverseString(str) { const res = []; for (let i = 0, len = str.length; i <= len; i++) res.push(str.charAt(len - i)); return res.join(""); } // Cut the string into characters and store the position of the character at the variable StateState function buildState(a) { let states = Array.from({ length: 2 * a.length }, () => State()); //caching let last = 0, start = 1; for (let i = 0; i < a.length; i++) { const char = a[i]; const cur = start; start++; states[cur].posStart = states[last].posStart + 1; let p = last; while (p !== -1 && !states[p].childs[char]) { states[p].childs[char] = cur; p = states[p].link; } if (p === -1) states[cur].link = 0; else { const q = states[p].childs[char]; if (states[p].posStart + 1 === states[q].posStart) states[cur].link = q; else { const clone = start; start++; //copy older element state states[clone].posStart = states[p].posStart + 1; states[clone].childs = { ...states[q].childs }; states[clone].link = states[q].link; while (p !== -1 && states[p].childs[char] === q) { states[p].childs[char] = clone; p = states[p].link; } states[q].link = clone; states[cur].link = clone; } } last = cur; } return states; } // build palindrome to look up function lookupPalin(s) { const len = s.length; let sx = "|"; // cut the string into pieces: ex: |h|e|l|l|o| const sxlen = len * 2 + 1; for (let i = 0; i < len; i++) sx += s[i] + "|"; let res = Array.from({ length: sxlen }, () => 0); let c = 0, r = 0, m = 0, n = 0; for (let i = 1; i < sxlen; i++) { if (i > r) { res[i] = 0; m = i - 1; n = i + 1; } else { const i2 = c * 2 - i; if (res[i2] < r - i) { res[i] = res[i2]; m = -1; } else { res[i] = r - i; n = r + 1; m = i * 2 - n; } } while (m >= 0 && n < sxlen && sx[m] === sx[n]) { res[i] += 1; m -= 1; n += 1; } if (i + res[i] > r) { r = i + res[i]; c = i; } } let result = Array.from({ length: len }, () => 0); for (let i = 1; i < sxlen - 1; i++) { const idx = parseInt((i - res[i]) / 2); result[idx] = Math.max(result[idx], res[i]); } return result; } // check ordre asc string function check(s, initial, posStart, size) { for (let i = 0; i < size; i++) { if (s[initial + i] !== s[posStart + i]) { if (s[initial + i] > s[posStart + i]) return true; // break; } } return false; } function solve(a, b) { const blen = b.length; const states = buildState(a); let plookup = lookupPalin(b); let apos = 0, start = -1, left = 0, mid = 0, total = 0, curlen = 0; // find the position's index of the palindrome start character for (let i = 0; i < blen; i++) { const char = b[i]; if (!states[apos].childs[char]) { while (apos !== -1 && !states[apos].childs[char]) apos = states[apos].link; if (apos === -1) { apos = 0; curlen = 0; continue; } curlen = states[apos].posStart; } curlen += 1; apos = states[apos].childs[char]; const new_start = i - curlen + 1; let new_mid = 0; if (i + 1 < blen) new_mid = plookup[i + 1]; const new_total = 2 * curlen + new_mid; //total length of such a substring palindrome if ( total < new_total || (total === new_total && check(b, start, new_start, curlen + mid)) ) { left = curlen; mid = new_mid; total = new_total; start = new_start; } } // find palindrome let palindrome = []; for (let i = 0; i < left + mid; i++) palindrome.push(b[start + i]); // push string containt le palindrome for (let i = left - 1; i > -1; i--) palindrome.push(palindrome[i]); // push string can be reverse in other string return palindrome.join(""); } function buildPalindrome(a, b) { const reverseB = reverseString(b); const res1 = solve(a, reverseB); const len1 = res1.length; const res2 = solve(reverseB, a); const len2 = res2.length; let res; if (len1 > len2) res = res1; else if (len1 < len2) res = res2; else res = res1 < res2 ? res1 : res2; if (res.length === 0) return -1; return res; } function main() { const ws = fs.createWriteStream(process.env.OUTPUT_PATH); const t = parseInt(readLine(), 10); for (let tItr = 0; tItr < t; tItr++) { const a = readLine(); const b = readLine(); let result = buildPalindrome(a, b); ws.write(result + "\n"); } ws.end(); }
HackerRank Build a Palindrome Solution in Scala
object Solution { import scala.io._ import scala.collection.SeqView class SuffixArray (_s: String) { val s = _s :+ 0.toChar val n = _s.length val alphabet_size = (_s.fold (0.toChar) ( (x, y) => x.max (y))).toInt + 1 private def counting_sort (m: Int, c: Array[Int], p: Seq[Int], o: Array[Int]): Unit = { val cnt:Array[Int] = Array.ofDim (m) p.foreach (pi => cnt(c(pi)) = cnt(c(pi)) + 1) (1 until m).foreach (i => cnt(i) = cnt(i) + cnt(i-1)) p.reverseIterator.foreach (pi => { cnt(c(pi)) = cnt(c(pi)) - 1; o(cnt(c(pi))) = pi; } ) } private def build ():Array[Int] = { val l = s.length var p: Array[Int] = Array.ofDim (l) var c = s.map (c => c.toInt).toArray var q: Array[Int] = Array.ofDim (l) counting_sort (alphabet_size, c, (0 until l), p) c(p(0)) = 0 var m = 0 for (i <- 1 until l) { if (s(p(i)) != s(p(i-1))) { m = m + 1 } c(p(i)) = m; } m = m + 1 var step = 1 while (step < l) { counting_sort (m, c, p.map (v => (v + l - step) % l), q) val t1 = p; p = q; q = t1 q(p(0)) = 0 m = 0 for (i <- 1 until l) { if (c(p(i)) != c(p(i-1)) || c((p(i) + step) % l) != c((p(i-1) + step) % l)) { m = m + 1 } q(p(i)) = m } m = m + 1 val t2 = c; c = q; q = t2 step = 2 * step } p.slice (1, l) } val o = build val r: Array[Int] = Array.ofDim (n); private def lcp_build () = { var q: Array[Int] = Array.ofDim (n) (0 until n).foreach (i => r(o(i)) = i) var l = 0 for (j <- 0 until n) { l = 0.max (l - 1) val i = r(j) if (i > 0) { val k = o(i - 1); while ((j + l < n) && (k + l < n) && s(j + l) == s(k + l)) { l = l + 1 } } else { l = 0 } q(i) = l } q } val lcp = lcp_build } val input = Source.stdin val inputit:Iterator[String] = input.getLines() var lineit:Iterator[String] = List.empty.iterator def rs() : String = { if (lineit.hasNext) lineit.next else { lineit = inputit.next.split(" ").iterator rs() } } def ri() : Int = rs().toInt class Solution (_a: String, _start: Int, _l1: Int, _l2: Int, _rank: Int) { val a = _a val start = _start val l1 = _l1 val l2 = _l2 val l = 2 * l1 + l2 val rank = _rank override def toString (): String = { val a = _a.slice (start, start + l1 + l2) ++ _a.slice (start, start + l1).reverse a } } def solve (a: String, b: String): List[Solution] = { var sols:Option[Solution] = None def update (a: String, start: Int, l1: Int, l2: Int, rank: Int) { val s = new Solution (a, start, l1, l2, rank) if (sols.isEmpty || sols.head.l < s.l || (sols.head.l == s.l && sols.head.rank > s.rank)) { sols = Some (s) } } val ra = a.reverse val z = new StringBuilder (a.length + b.length + 1) z.append (a) z.append (1.toChar) z.append (b.reverse) val sb = new SuffixArray (z.toString) val n = a.length val p: Array[Int] = Array.fill (n + 1)(0) for (t <- 0 to 1) { //t = 0 -> odd length palindrome var l = 0 var r = -1 + t val d: Array[Int] = Array.ofDim (n) for (i <- t until n) { var k = if (i > r) 0 else Math.min (d (l + r - i + t), r - i + t) + 1 while (i + k - t < n && i - k >= 0 && a (i + k - t) == a (i - k)) { k = k + 1 } d (i) = k - t k = k - 1 p(i-k) = p(i-k).max ( (i + k - t) - (i - k) + 1) if (i + k - t > r) { l = i - k r = i + k - t } } for (i <- 1 to n) { p(i) = p(i).max (p(i-1) - 2) } } def f (start: Int, l: Int, rank: Int) = { assert (start < n) if (l > 0) { update (a, start, l, p (start + l), rank) } } var cur_l = 0 for (i <- 0 until sb.n) { if (sb.o(i) < n) { cur_l = cur_l.min (sb.lcp(i)) f (sb.o(i), cur_l, i) } else if (sb.o(i) > n) { cur_l = Int.MaxValue } } cur_l = 0 for (i <- sb.n - 2 to 0 by -1) { if (sb.o(i) < n) { cur_l = cur_l.min (sb.lcp(i+1)) f (sb.o(i), cur_l, i) } else if (sb.o(i) > n) { cur_l = Int.MaxValue } } sols.toList } def main(args: Array[String]) { val nt = ri () for (t <- 1 to nt) { val s = rs () val t = rs () val sols = solve (s, t).toList ++ solve (t.reverse, s.reverse).toList if (sols.isEmpty) { println (-1) } else { println (sols.map(_.toString).minBy (s => (-s.length, s))) } } } }
HackerRank Build a Palindrome Solution in Pascal
{$MAXSTACKSIZE $5FFFFFFF} uses MATH; const MAX_SIZE = 1000; //const MAX_SIZE = 500000;// 5 * 10^5 // 12345 // ############################# // STRING type TStr = record str : array [ 1 .. MAX_SIZE ] of char; size : LongInt; end; procedure getStr ( const SS : ansiString ; var s : TStr ) ; var i : LongInt; begin s.size := length(SS); for i := 1 to s.size do s.str[i] := ss[i]; end; procedure append ( var s : TStr ; c : char ) ; begin inc ( s.size ) ; s.str [ s.size ] := c; end; procedure concat ( var s : TStr ; const Sec : TStr ) ; var i : LongInt; begin for i := 1 to Sec.size do append ( s , Sec.str[i] ) ; end; procedure priStr ( const S : TStr ) ; var i : LongInt; begin for i := 1 to S.size do write ( S.str[i] ) ; writeLn(); end; // END OF STRING // ############################# // ############################# // SUFIX ARRAY type TSA = array [ 1 .. MAX_SIZE ] of LongInt; var CLASS_ : Array [ 0 .. 32 , 1 .. MAX_SIZE ] of LongInt; CLASS_START : Array [ 1 .. MAX_SIZE ] of LongInt; procedure InitSA ( const S : TStr ; var SA : TSA ) ; var Cnt : Array [ #0 .. #255 ] of LongInt; i : LongInt; c : char; classCnt : LongInt; begin for c := #0 to #255 do Cnt[c] := 0; for i :=1 to S.size do inc ( Cnt [ S.str[i] ] ) ; Cnt[#0] := 1; for c := #2 to #255 do Cnt[c] := Cnt[c] + Cnt[ Chr ( ord ( c ) - 1 ) ] ; for i := 1 to S.size do begin SA[ Cnt [ S.str[i] ] ] := i ; dec ( Cnt [ S.str[i] ] ) ; end; CLASS_[0][SA[1]] := 1; CLASS_START[1] := 1; classCnt := 1; for i := 2 to S.size do begin if ( s.str[SA[i]] <> s.str[SA[i-1]] ) then begin inc ( classCnt ) ; CLASS_START[classCnt] := i; end; CLASS_[0][SA[i]] := classCnt; end; end; procedure DoSA ( var SA : TSA ; h , n : LongInt ) ; var NEW_SA : TSA; procedure push ( x , h : LongInt ) ; begin if ( x - 1 shl h >= 1 ) then x := x - 1 shl h else x := n + ( x - 1 shl h ) ; NEW_SA [ CLASS_START [ CLASS_[h][x] ] ] := x; inc ( CLASS_START [ CLASS_[h][x] ] ) ; end; function getFrw ( x , h : LongInt ) : LongInt ; begin if ( x + 1 shl h <= n ) then x := x + 1 shl h else x := (x + 1 shl h) mod n; getFrw := x; end; var i : LongInt; classCnt : LongInt; begin for i := 1 to N do begin push ( SA[i] , h ) ; end; // restore CLASS_[h+1][NEW_SA[1]] := 1; CLASS_START[1] := 1; classCnt := 1; for i := 2 to N do begin if ( CLASS_[h][NEW_SA[i]] = CLASS_[h][NEW_SA[i-1]] ) then begin // same last class // diffrent other part if ( CLASS_[h][ getFrw ( NEW_SA[i] , h) ] = CLASS_[h][ getFrw ( NEW_SA[i-1] , h ) ] ) then begin CLASS_[h+1][NEW_SA[i]] := CLASS_[h+1][NEW_SA[i-1]]; end else begin inc ( classCnt ) ; CLASS_[h+1][NEW_SA[i]] := classCnt; CLASS_START[classCnt] := i; end; end else begin inc ( classCnt ) ; CLASS_[h+1][NEW_SA[i]] := classCnt; CLASS_START[classCnt] := i; end; end; move ( NEW_SA , SA , SIZEOF ( TSA ) ) ; if ( 1 shl (h+1) > n ) then exit(); DoSA ( SA , h+1 , n ) ; end; // END OF SUFIX ARRAY // ############################# procedure priSuf ( const S : TStr ; x : LongInt ) ; begin write ( x , ' - ' ) ; while ( x <= S.size ) do begin write ( s.str[x] ); inc ( x ) ; end; writeLn(); end; function lcp ( i , j ,n : LongInt ) : LongInt; var ans : LongInt; k : LongInt; begin ans := 0 ; for k := 30 downto 0 do begin if ( 1 shl k <= n ) then begin if ( CLASS_[k][i] = CLASS_[k][j] ) then begin ans := ans + 1 shl k; i := i + 1 shl k; j := j + 1 shl k; end; end; end; exit ( ans ) ; end; var s : TStr; SA : TSA; ANS_STR : AnsiString; First : LongInt; procedure TryThis ( i , j : LongInt ) ; var x , cp , tail , head : LongInt; begin tail := 0 ; head := 0 ; cp := lcp ( i , j , S.size ) ; if ( i+cp <= First ) then tail := 1 ; if ( S.str[j+cp] >= 'a' ) then begin if ( tail = 0 ) or ( S.str[i+cp] > S.str[j+cp] ) then begin tail := 0; head := 1; end; end; //writeLn ( i , ' ' , j , ' ' , tail , ' ' , head ) ; if ( cp * 2 + tail + head > length(ANS_STR) ) then begin ANS_STR := ''; for x := i to i+cp+tail-1 do ANS_STR := ANS_STR + S.str[x]; for x := j+cp-1+head downto j do ANS_STR := ANS_STR + S.str[x]; end; end; procedure solve(); var i , j : LongInt; FIRST_STR , SECOND_STR : ansiString; begin ANS_STR := ''; readLn ( FIRST_STR ) ; readLn ( SECOND_STR ) ; if ( Length(FIRST_STR) + Length(SECOND_STR) > 500 ) then begin writeLn ( -1 ) ; exit(); end; First := Length(FIRST_STR); s.size := 0; getStr ( FIRST_STR , s ) ; append ( s , #3 ) ; for i := Length(SECOND_STR) downto 1 do append ( s , SECOND_STR[i] ) ; append ( s , #4 ) ; //priStr ( s ) ; InitSA ( s , SA ) ; DoSA ( SA , 0 , s.size ) ; { for i := 1 to S.size do begin priSuf ( s , SA[i] ) ; end; } for i := 1 to S.size-1 do begin if ( min ( SA[i] , SA[i+1] ) <= First )then begin if ( max ( SA[i] , SA[i+1] ) >= First+2 ) then begin TryThis ( min ( SA[i] , SA[i+1] ) , max ( SA[i] , SA[i+1] ) ) ; end; end; end; { for i := 1 to First do begin for j := First + 2 to S.size do begin TryThis ( i , j ) ; end; end; } if ( Length(ANS_STR) < 2 ) then writeLn ( -1 ) else writeLn ( ANS_STR ) ; end; var t , ct : LongInt; begin readLn ( t ) ; for ct := 1 to t do begin solve(); end; end.
Disclaimer: This problem (Build a Palindrome) is generated by HackerRank but the solution is provided by Chase2learn. This tutorial is only for Educational and Learning purposes.