Hello Programmers, In this post, you will Know 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 directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
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
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;
}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;
}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;
}
}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)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();
}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)))
}
}
}
}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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.