HackerRank Build a Palindrome Problem Solution Yashwant Parihar, May 1, 2023May 6, 2023 In this post, we will solve HackerRank Build a Palindrome Problem Solution. You have two strings, a and b. Find a string, s, such that: s can be expressed as s = 8a+ st where 8, is a non-empty substring of a and so is a non-empty substring of b. $ is a palindromic string.The length of $ is as long as possible.For each of the q pairs of strings (a and b) received as input, find and print strings, on anew line. If you’re able to form more than one valid string $;, print whichever one comesfirst alphabetically. If there is no valid answer, print -1 instead.Input FormatThe first line contains a single integer, q, denoting the number of queries. The subsequentlines describe each query over two lines: The first line contains a single string denoting a. The second line contains a single string denoting b. Output FormatFor each pair of strings (a and b), find some s; satisfying the conditions above and print iton 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 ExplanationWe perform the following three queries: Concatenate s₁ = “a” with s = “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 s = “dfh” with s¿ = “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 Problem Solution Build a Palindrome C Solution #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<limits.h> #define SWAP(_X, _Y, __type) \ do{ \ __type __tmp = _X; \ _X = _Y; \ _Y = __tmp; \ }while(0) #define MAX(__X, __Y) ((__X) > (__Y) ? (__X) : (__Y)) #define MIN(__X, __Y) ((__X) < (__Y) ? (__X) : (__Y)) struct interval { int mid; int odd; int begin; int end; }; int icmp(const void *p1, const void *p2) { const struct interval *i1 = p1; const struct interval *i2 = p2; if( i1 -> begin < i2 -> begin ) { return -1; } else if( i1 -> begin > i2 -> begin ) { return 1; } return 0; } int *_find_longest_palindromes(int *radius[2], int len) { int *result; struct interval *intervals; int num_intervals = 0; result = malloc(sizeof(*result) * len); for( int i = 0 ; i < len ; ++i ) { result[i] = 1; } intervals = malloc(sizeof(*intervals) * len * 2); for( int j = 0 ; j < 2 ; ++j ) { for( int i = 0 ; i < len ; ++i ) { if( radius[j][i] != 0 ) { intervals[num_intervals].odd = j; intervals[num_intervals].mid = i; intervals[num_intervals].begin = intervals[num_intervals].mid - radius[j][i]; intervals[num_intervals].end = intervals[num_intervals].mid - 1; ++num_intervals; } } } if( num_intervals > 0 ) { int _num_intervals = 1; qsort(intervals, num_intervals, sizeof(*intervals), icmp); for( int i = 1 ; i < num_intervals ; ++i ) { if( intervals[_num_intervals - 1].end < intervals[i].begin ) { intervals[_num_intervals++] = intervals[i]; } else if( intervals[_num_intervals - 1].end <= intervals[i].end ) { if( intervals[i].begin == intervals[_num_intervals - 1].begin && ( intervals[_num_intervals - 1].end < intervals[i].end || intervals[i].odd ) ) { intervals[_num_intervals - 1] = intervals[i]; } else { intervals[_num_intervals - 1].end = intervals[i].begin - 1; intervals[_num_intervals++] = intervals[i]; } } } num_intervals = _num_intervals; } for( int i = 0 ; i < num_intervals ; ++i ) { for( int j = intervals[i].begin ; j <= intervals[i].end ; ++j ) { result[j] = 2 * ( intervals[i].mid - j ) + intervals[i].odd; } } free(intervals); return result; } int* find_longest_palindromes(const char *s, int len) { int *result, *radius[2]; 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, 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; } int * LCP(const char *s, int len, int *sa) { int k = 0; int *lcp, *rank; lcp = calloc(len, sizeof(*lcp)); rank = calloc(len, sizeof(*rank)); for( int i = 0 ; i < len ; ++i ) { rank[sa[i]] = i; } for( int i = 0 ; i < len ; ++i ) { if( rank[i] == len - 1 ) { k = 0; } else { int j = sa[rank[i] + 1]; while( i + k < len && j + k < len && s[i+k] == s[j+k] ) { k++; } lcp[rank[i]] = k; } if( k != 0 ) { --k; } } free(rank); return lcp; } struct state { int suffix; int bucket[2]; }; int * SA(const char *s, int len) { int *p = malloc(sizeof(int) * len); int *sa = malloc(sizeof(int) * len); struct state *state, *tmp; state = malloc(sizeof(*state) * len); tmp = malloc(sizeof(*tmp) * len); for( int i = 0 ; i < len ; ++i ) { p[i] = s[i] - 0x60 + 1; } for( int h = 1 ; h < len ; h <<= 1 ) { for( int i = 0 ; i < len ; ++i ) { state[i].suffix = i; state[i].bucket[0] = p[i]; if( i + h < len ) { state[i].bucket[1] = p[i+h]; } else { state[i].bucket[1] = 0; } } for( int i = 1 ; i >= 0 ; --i ) { for( int div = 1 ; MAX(len, 28) / div > 0 ; div *= 10 ) { int count[10] = {0}; for( int j = 0 ; j < len ; ++j ) { ++count[(state[j].bucket[i] / div) % 10]; } for( int j = 1 ; j < 10 ; ++j ) { count[j] += count[j-1]; } for( int j = len - 1 ; j >= 0 ; --j ) { register int index = ( state[j].bucket[i] / div ) % 10; tmp[--count[index]] = state[j]; } SWAP(tmp, state, struct state *); } } for( int i = 0, bucket = 0 ; i < len ; ++i ) { if( ( h << 1 ) >= len || i == 0 || state[i-1].bucket[0] != state[i].bucket[0] || state[i-1].bucket[1] != state[i].bucket[1] ) { ++bucket; } p[state[i].suffix] = bucket; } } free(state); free(tmp); for( int i = 0 ; i < len ; ++i ) { sa[p[i]-1] = i; } free(p); return sa; } char *build_palindrome(const char *a, const char *b) { int alen = strlen(a), blen = strlen(b), *sa, *lcp, *p, *lcp_ab, maxlen = 0, suffix = -1; char *result = NULL; int slen = alen + blen + 1; char *s = malloc(sizeof(char) * ( slen + 1 )); memcpy(s, a, alen); s[alen] = 0x60; for( int i = 0 ; i < blen ; ++i ) { s[alen+1+i] = b[blen-1-i]; } s[slen] = '\0'; sa = SA(s, slen); lcp = LCP(s, slen, sa); lcp_ab = calloc(slen, sizeof(*lcp_ab)); int i = 1; while( i < slen - 1 ) { if( lcp[i] && ( ( sa[i] > alen && sa[i+1] < alen ) || ( sa[i] < alen && sa[i+1] > alen ) ) ) { int j, current = lcp[i]; for( j = i ; j > 0 && ( ( sa[i] > alen ) ? ( sa[j] > alen ) : ( sa[j] < alen ) ) && lcp[j] > 0 ; --j ) { current = MIN(current, lcp[j]); lcp_ab[j] = MAX(lcp_ab[j], current); } current = lcp[i]; for( j = i + 1 ; j < slen && ( ( sa[i] > alen ) ? ( sa[j] < alen ) : ( sa[j] > alen ) ) && lcp[j-1] > 0 ; ++j ) { lcp_ab[j] = current = MIN(current, lcp[j - 1]); } i = j - 1; } else { ++i; } } p = find_longest_palindromes(s, slen); for( int i = 1 ; i < slen ; ++i ) { if(lcp_ab[i]) { int len = 2 * lcp_ab[i]; if( ( sa[i] < alen && sa[i] + lcp_ab[i] < alen ) || ( sa[i] > alen && sa[i] + lcp_ab[i] < slen ) ) { len += p[sa[i] + lcp_ab[i]]; } if( len > maxlen ) { suffix = i; maxlen = len; } } } if(maxlen) { int len = 0; result = malloc(sizeof(*result) * ( maxlen + 1 )); memcpy(result, s + sa[suffix], lcp_ab[suffix]); if( maxlen > lcp_ab[suffix] * 2 ) { memcpy(result + lcp_ab[suffix], s + sa[suffix] + lcp_ab[suffix], maxlen - lcp_ab[suffix] * 2); } for( int i = 0 ; i < lcp_ab[suffix] ; ++i ) { result[maxlen-lcp_ab[suffix]+i] = s[sa[suffix] + lcp_ab[suffix]-1-i]; } result[maxlen] = '\0'; } free(sa); free(lcp); free(lcp_ab); free(p); free(s); return result; } int main() { int n; scanf("%d", &n); while( n-- != 0 ) { char *a, *b, *p; a = malloc(131072 * sizeof(*a)); b = malloc(131072 * sizeof(*b)); scanf("%s", a); scanf("%s", b); p = build_palindrome(a, b); if( p == NULL ) { printf("-1\n"); } else { printf("%s\n", p); } free(p); free(a); free(b); } return 0; } Build a Palindrome C++ Solution #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <string> #include <list> #include <memory> #include <unordered_map> #include <functional> namespace algorithm_lib { class longest_palindromic_substring_t { public: static std::vector<size_t> max_lengths(const std::string& input) { if (input.empty()) return std::vector<size_t>(); auto input_with_boundaries = add_boundaries(input); std::vector<size_t> radius(input_with_boundaries.size()); size_t reference_boundary = 2; size_t reference_center = 1; radius[0] = 0; radius[1] = 1; for (size_t k = 2; k < input_with_boundaries.size(); ++k) { size_t mirror_radius = radius[reference_center * 2 - k]; if (k + mirror_radius < reference_boundary) { radius[k] = mirror_radius; } else { reference_center = k; size_t r = std::max(reference_boundary, k) - k; while (reference_center > r && reference_center + r < input_with_boundaries.size() - 1 && input_with_boundaries[reference_center - r - 1] == input_with_boundaries[reference_center + r + 1]) ++r; radius[k] = r; reference_boundary = k + r; } } reference_boundary = input_with_boundaries.size() - 1; std::vector<size_t> output(input.size()); for (size_t k = input_with_boundaries.size() - 2; k != 0; --k) { size_t new_boundary = k - radius[k]; while (reference_boundary > new_boundary) { reference_boundary -= 2; output[reference_boundary / 2] = k - reference_boundary; } } return output; } private: static std::string add_boundaries(const std::string& input) { std::string output; for (auto c : input) { output.push_back('|'); output.push_back(c); } output += '|'; return output; } }; } namespace algorithm_lib { class suffix_tree_t { private: class node_t { public: size_t start; std::shared_ptr<size_t> end; std::unordered_map<char, std::shared_ptr<node_t>> children; node_t(size_t start, std::shared_ptr<size_t> end) : start(start), end(end) {} }; typedef std::shared_ptr<node_t> nodeptr; private: nodeptr _root; std::string _text; public: suffix_tree_t(const std::string& text) : _text(text) , _root(std::make_shared<node_t>(-1, nullptr)) { size_t suffix_count = 0; auto end = std::make_shared<size_t>(text.size()); for (size_t k = 0; k < text.size(); ++k) { ++suffix_count; do { if (false == create_internal_node(_root, suffix_count - 1, k, end)) break; } while (--suffix_count); } } std::string max_repeated_substring() { std::string max_path; size_t max_length = 0; traverse([&]( const std::string& path, size_t path_length, size_t start, size_t end, const std::vector<size_t>& children_starts) { if (path_length > max_length) { max_length = path_length; max_path = path; } }); return full_path(max_path); } std::string full_path(const std::string& path) { auto node = _root; std::string r; for (auto c : path) { auto child = node->children[c]; r += _text.substr(child->start, *child->end - child->start); node = child; } return r; } void traverse(const std::function<void( const std::string& path, size_t path_length, size_t start, size_t end, const std::vector<size_t>& children_starts)>& callback) { struct item_t { std::string path; size_t length; nodeptr node; item_t(const std::string& path, size_t length, nodeptr node) : path(path), length(length), node(node) {} }; std::list<item_t> queue; queue.push_back(item_t("", 0, _root)); while (!queue.empty()) { auto parent = queue.front(); queue.pop_front(); std::vector<size_t> starts; for (auto child : parent.node->children) { starts.push_back(child.second->start); if (child.second->children.size() == 0) continue; queue.push_back( item_t( parent.path + child.first, parent.length + *child.second->end - child.second->start, child.second)); } if(parent.node != _root) callback(parent.path, parent.length, parent.node->start, *parent.node->end, starts); } } private: bool create_internal_node(nodeptr parent, size_t depth, size_t pos, std::shared_ptr<size_t> end) { nodeptr child; auto new_leaf = std::make_shared<node_t>(pos, end); while(child = parent->children[_text[pos - depth]]) { auto edge_length = *child->end - child->start; if (edge_length > depth) { if (_text[child->start + depth] == _text[pos]) return false; auto internal_node = std::make_shared<node_t>( child->start, std::make_shared<size_t>(child->start + depth)); parent->children[_text[pos - depth]] = internal_node; child->start = *internal_node->end; internal_node->children[_text[*internal_node->end]] = child; internal_node->children[_text[pos]] = new_leaf; return true; } depth -= edge_length; parent = child; } parent->children[_text[pos - depth]] = new_leaf; return true; } }; } namespace build_a_palindrome { inline std::string solve(const std::string& a, const std::string& b) { std::string rb(b.crbegin(), b.crend()); std::string c = a + "#" + rb + "$"; auto pa = algorithm_lib::longest_palindromic_substring_t::max_lengths(a); auto pb = algorithm_lib::longest_palindromic_substring_t::max_lengths(rb); pa.push_back(0); pb.push_back(0); algorithm_lib::suffix_tree_t tree(c); std::string max_path; size_t max_length = 0; size_t max_start; auto construct_palidrome = [&](const std::string& path, size_t child_start) { auto full_path = tree.full_path(path); std::string palidrome; if (child_start <= a.size()) palidrome = c.substr(child_start, pa[child_start]); else palidrome = c.substr(child_start, pb[child_start - 1 - a.size()]); return full_path + palidrome + std::string(full_path.crbegin(), full_path.crend()); }; tree.traverse([&]( const std::string& path, size_t path_length, size_t start, size_t end, const std::vector<size_t>& children_starts) { size_t current_length = 0; std::string current_path; size_t current_start; bool left = false; bool right = false; for (auto start : children_starts) { size_t palindrome_length; if (start <= a.size()) { left = true; palindrome_length = pa[start]; } else { right = true; palindrome_length = pb[start - a.size() - 1]; } auto length = path_length * 2 + palindrome_length; if (length < std::max(current_length, max_length)) continue; if (length > current_length || c[start] < c[current_start] || c[start] == c[current_start] && c.substr(start, palindrome_length) < c.substr(current_start, palindrome_length)) { current_length = length; current_path = path; current_start = start; } } if (false == left || false == right) return; if (current_length < max_length) return; if (current_length > max_length || construct_palidrome(current_path, current_start) < construct_palidrome(max_path, max_start)) { max_length = current_length; max_path = current_path; max_start = current_start; } }); return max_path.empty() ? "-1" : construct_palidrome(max_path, max_start); } inline void solve() { int t; std::cin >> t; while (t--) { std::string a, b; std::cin >> a >> b; std::cout << solve(a, b) << std::endl; } } } int main() { build_a_palindrome::solve(); return 0; } Build a Palindrome C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { /* * Complete the buildPalindrome function below. */ static string buildPalindrome(string a, string b) { int max, n1 = a.Length, n2 = b.Length, c, size = 1, nn; max = 1; int[] poli1 = new int[n1]; int[] poli2 = new int[n2]; for (int i = 1; i < n1; i++) { nn = 1; poli1[i - 1] = 1; while (i + nn < n1 && i - nn >= 1 && a[i - nn] == a[i + nn]) { poli1[i - nn - 1] = 2 * nn + 1; nn++; } nn = 1; while (i + nn < n1 && i - nn + 1 >= 1 && a[i - nn + 1] == a[i + nn]) { poli1[i - nn] = 2 * nn; nn++; } } for (int i = n2 - 2; i >= 0; i--) { nn = 1; poli2[i + 1] = 1; while (i + nn < n2 - 1 && i - nn >= 0 && b[i - nn] == b[i + nn]) { poli2[i + nn + 1] = 2 * nn + 1; nn++; } nn = 1; while (i - nn >= 0 && i + nn - 1 < n2 - 1 && b[i - nn] == b[i + nn - 1]) { poli2[i + nn] = 2 * nn; nn++; } } string s1 = "", s2; var ar = new ValueTuple<int, int>[250000, 27]; var dic = new int[n1+1]; int previous = 0; a += '{'; for (int i = 0; i < n1; i++) { int y = i, cur = 0; c = a[y] - 'a'; if (ar[0, c].Item1 == 0) { dic[i] = i; ar[0, c] = (size, y); size++; continue; } else { while (ar[cur, c].Item1 != 0) { previous = ar[cur, c].Item2; if (poli1[previous] < poli1[y]) ar[cur, c].Item2 = y; else if (poli1[previous] == poli1[y]) if (string.CompareOrdinal(a.Substring(previous + 1, poli1[previous]), a.Substring(y + 1, poli1[y])) > 0) ar[cur, c].Item2 = y; cur = ar[cur, c].Item1; y++; c = a[y] - 'a'; } while (a[y] == a[previous + 1]) { c = a[y] - 'a'; int ek = poli1[previous + 1] > poli1[y] ? previous + 1 : poli1[previous + 1] < poli1[y] ? y : string.CompareOrdinal(a.Substring(previous + 2, poli1[previous + 1]), a.Substring(y + 1, poli1[y])) < 0 ? previous+1 : y; ar[cur, c] = (size, ek); cur = size; size++; y++; previous++; } c = a[y] - 'a'; ar[cur, c] = (size, y); dic[i] = y; size++; c = a[previous + 1] - 'a'; if (ar[cur, c].Item1 == 0) { ar[cur, c] = (size++, previous+1); dic[previous+1 - y + i] = previous+1; } } } nn = poli1.Max(); var map = new Dictionary<int, ValueTuple<int, int, int>>(); var tt = (0, 0, 0); map.Add(0, tt); int n3, n4, n5 = 0, z; size = 1; b = b.Insert(0, "{"); for (int i = n2; i >= 1; i--) { c = b[i] - 'a'; if (ar[0, c].Item1 == 0) continue; int cur = 0, j = i; while (ar[cur, c].Item1 != 0 && j != 0) { n5 = ar[cur, c].Item2; cur = ar[cur, c].Item1; j--; c = b[j] - 'a'; } while (a[n5 + 1] == b[j] && j != 0) { n5++; j--; } n4 = i - j; if (n4 > 0) { n3 = 2 * n4 + Math.Max(poli1[n5], poli2[j]); if (n3 < max) continue; else if (n3 > max) { n2 = Math.Max(n2, (max - nn) / 2); map[0] = (n5, j, n4); max = n3; size = 1; } else if (n3 == max && size < map.Count) map[size++] = (n5, j, n4); else map.Add(size++, (n5, j, n4)); } int pr = n5 - n4 + 2; while (dic[pr] <= n5 && pr < n1 && i > 0 ) { pr++; i--; } } if (map[0].Item3 == 0) return "-1"; n5 = map[0].Item1; z = map[0].Item2; n4 = map[0].Item3; int a1 = poli1[n5], a2 = poli2[z]; s1 = a1 > a2 ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) : (a1 == a2 && string.CompareOrdinal(a.Substring(n5 + 1, a1), b.Substring(z - a2 + 1, a2)) < 0) ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) : string.Concat(a.Substring(n5 - n4 + 1, n4), b.Substring(z - a2 + 1, n4 + a2)); while (size - 1 > 0) { n5 = map[size - 1].Item1; z = map[size - 1].Item2; n4 = map[size - 1].Item3; a1 = poli1[n5]; a2 = poli2[z]; s2 = a1 > a2 ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) : (a1 == a2 && string.CompareOrdinal(a.Substring(n5 + 1, a1), b.Substring(z - a2 + 1, a2)) < 0) ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) : string.Concat(a.Substring(n5 - n4 + 1, n4), b.Substring(z - a2 + 1, n4 + a2)); if (string.CompareOrdinal(s1, s2) > 0) s1 = s2; size--; } return s1; } static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); int t = Convert.ToInt32(Console.ReadLine()); for (int tItr = 0; tItr < t; tItr++) { string a = Console.ReadLine(); string b = Console.ReadLine(); string result = buildPalindrome(a, b); textWriter.WriteLine(result); } textWriter.Flush(); textWriter.Close(); } } Build a Palindrome Java Solution import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { static int N = 100000; static int M = 4 * N + 3; static char[] a = new char[M]; static int[] sa = new int[M]; static int[] isa = new int[M]; static void iota(int v[], int end, int val) { for (int i = 0; i < end; i++) { v[i] = val++; } } static void suffixArray(int n, int m, int h[], int x[]) { Arrays.fill(h, 0, m, 0); for (int i = 0; i < n; i++) { isa[i] = a[i]; } for (int i = 0; i < n; i++) { h[isa[i]]++; } for (int i = 1; i < m; i++) { h[i] += h[i - 1]; } for (int i = n; --i >= 0; ) { sa[--h[isa[i]]] = i; } int k = 1; for (; ; k <<= 1) { iota(x, k, n - k); int j = k; for (int i = 0; i < n; i++) { if (sa[i] >= k) { x[j++] = sa[i] - k; } } Arrays.fill(h, 0, m, 0); for (int i = 0; i < n; i++) { h[isa[x[i]]]++; } for (int i = 1; i < m; i++) { h[i] += h[i - 1]; } for (int i = n; --i >= 0; ) { sa[--h[isa[x[i]]]] = x[i]; } Arrays.fill(h, 0, m, 0); m = 1; h[sa[0]] = 0; for (int i = 1; i < n; i++) { if (isa[sa[i]] != isa[sa[i - 1]] || Math.max(sa[i], sa[i - 1]) >= n - k || isa[sa[i] + k] != isa[sa[i - 1] + k]) { m++; } h[sa[i]] = m - 1; } System.arraycopy(h, 0, isa, 0, n); if (m == n) { break; } } k = 0; h[0] = 0; for (int i = 0; i < n; i++) { if (isa[i] > 0) { for (int j = sa[isa[i] - 1]; i + k < n && j + k < n && a[i + k] == a[j + k]; k++) ; h[isa[i]] = k; if (k > 0) { k--; } } } } static int[][] tab = new int[19][M]; static int lcp(int x, int y) { if (x < 0 || y < 0) { return 0; } x = isa[x]; y = isa[y]; if (x > y) { int t = x; x = y; y = t; } x++; int k = 0; while (1 << k + 1 < y - x + 1) { k++; } return Math.min(tab[k][x], tab[k][y - (1 << k) + 1]); } static long[] z = new long[2 * N + 1]; static int[] len = new int[N]; static void manacher(int from, int n) { int m = 2 * n + 1; z[0] = 1; for (int f = 0, g = 0, i = 1; i < m; i++) { if (i < g && z[2 * f - i] != g - i) { z[i] = Math.min(z[2 * f - i], g - i); } else { g = Math.max(g, f = i); for (; g < m && 2 * f - g >= 0 && (g % 2 == 0 || a[from + (2 * f - g) / 2] == a[from + g / 2]); g++) { len[(g - 1) / 2] = g - f; } z[f] = g - f; } } } static int[] L = new int[M]; static int[] R = new int[M]; static char[] buildPalindrome(char[] a1, char[] b) { int na = a1.length; System.arraycopy(a1, 0, a, 0, na); a[na] = 0; int ra = na + 1; for (int i = 0; i < na; i++) { a[ra + i] = a[na - 1 - i]; } a[ra + na] = 1; int nb = b.length; int b0 = ra + na + 1; System.arraycopy(b, 0, a, b0, nb); a[b0 + nb] = 2; int rb = b0 + nb + 1; for (int i = 0; i < nb; i++) { a[rb + i] = b[nb - 1 - i]; } int n = 2 * na + 2 * nb + 3; suffixArray(n, 'z' + 1, tab[0], L); for (int i = 1; 1 << i < n; i++) { for (int j = n - (1 << i); j > 0; j--) { tab[i][j] = Math.min(tab[i - 1][j], tab[i - 1][j + (1 << i - 1)]); } } int bma = na + 1 + na + 1; for (int i = 0; i < n; i++) { if (bma <= sa[i] && sa[i] < bma + nb) { L[i] = sa[i]; } else { L[i] = i > 0 ? L[i - 1] : -1; } } for (int i = n; --i >= 0; ) { if (bma <= sa[i] && sa[i] < bma + nb) { R[i] = sa[i]; } else { R[i] = i + 1 < n ? R[i + 1] : -1; } } manacher(na + 1, na); int opt = 0; int optp = 0; int optx = 0; int opty = 0; for (int i = 0; i < na; i++) { int pal = i > 0 ? len[i - 1] : 0; int ii = na + 1 + i; int j = L[isa[ii]]; if (lcp(ii, R[isa[ii]]) > lcp(ii, j)) j = R[isa[ii]]; int comm = lcp(ii, j); if (comm > 0) { int len = pal + 2 * comm; int pos = na - (i + comm); if (len > opt || len == opt && isa[pos] < isa[optp]) { opt = len; optp = pos; optx = pal + comm; opty = comm; } } } for (int i = 0; i < n; i++) { if (na + 1 <= sa[i] && sa[i] < na + 1 + na) { L[i] = sa[i]; } else { L[i] = i > 0 ? L[i - 1] : -1; } } for (int i = n; --i >= 0; ) { if (na + 1 <= sa[i] && sa[i] < na + 1 + na) { R[i] = sa[i]; } else { R[i] = i + 1 < n ? R[i + 1] : -1; } } manacher(bma, nb); for (int i = 0; i < nb; i++) { int pal = i > 0 ? len[i - 1] : 0; int ii = bma + i; int j = L[isa[ii]]; if (lcp(ii, R[isa[ii]]) > lcp(ii, j)) { j = R[isa[ii]]; } int comm = lcp(ii, j); if (comm > 0) { int len = pal + 2 * comm, pos = n - (i + comm); if (len > opt || len == opt && isa[pos] < isa[optp]) { opt = len; optp = pos; optx = comm; opty = pal + comm; } } } if (opt == 0) { return "-1".toCharArray(); } char[] result = new char[optx + opty]; for (int i = 0; i < optx; i++) { result[i] = a[optp + i]; } for (int i = 0; i < opty; i++) { result[optx + i] = a[optp + opty - i - 1]; } return result; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int t = Integer.parseInt(st.nextToken()); for (int tItr = 0; tItr < t; tItr++) { char[] a = br.readLine().toCharArray(); char[] b = br.readLine().toCharArray(); bw.write(buildPalindrome(a, b)); bw.newLine(); } bw.close(); br.close(); } } Build a Palindrome JavaScript Solution 'use strict'; const fs = require('fs'); process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', function(inputStdin) { inputString += inputStdin; }); process.stdin.on('end', function() { inputString = inputString.split('\n'); main(); }); function readLine() { return inputString[currentLine++]; } /* * Complete the 'buildPalindrome' function below. * * The function is expected to return a STRING. * The function accepts following parameters: * 1. STRING a * 2. STRING b */ function State() { return { link: -1, posStart: 0, childs: {}, }; } function reverseString(str) { let res = ''; for (let i = str.length - 1; i >= 0; i--) { res += str[i]; } return res; } // 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().trim(), 10); for (let tItr = 0; tItr < t; tItr++) { const a = readLine(); const b = readLine(); const result = buildPalindrome(a, b); ws.write(result + '\n'); } ws.end(); } Build a Palindrome Python Solution def build_palindrome_lookup(s): sx = '|' + '|'.join(s) + '|' sxlen = len(sx) rslt = [0] * sxlen c, r, m, n = 0, 0, 0, 0 for i in range(1, sxlen): if i > r: rslt[i] = 0 m = i - 1 n = i + 1 else: i2 = c * 2 - i if rslt[i2] < r - i: rslt[i] = rslt[i2] m = -1 else: rslt[i] = r - i n = r + 1 m = i * 2 - n while m >= 0 and n < sxlen and sx[m] == sx[n]: rslt[i] += 1 m -= 1 n += 1 if i + rslt[i] > r: r = i + rslt[i] c = i res = [0] * len(s) for i in range(1, sxlen - 1): idx = (i - rslt[i]) // 2 res[idx] = max(res[idx], rslt[i]) return res class state: def __init__(self): self.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 range(2 * n)] st[0].link = -1 st[0].length = 0 last = 0 sz = 1 last, sz = build_part_st(a, st, 1, last, sz) plookup = build_palindrome_lookup(b) apos, start, left, mid, total, curlen = 0, -1, 0, 0, 0, 0 for i in range(blen): c = b[i] if c not in st[apos].childs: while apos!=-1 and c not in st[apos].childs: 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 range(left + mid): palindrome.append(b[start + i]) for i in range(left - 1, -1, -1): palindrome.append(palindrome[i]) return ''.join(palindrome) def lex_gt(s, old_start, new_start, size): for i in range(size): if s[old_start + i] != s[new_start + i]: if s[old_start + i] > s[new_start + i]:# old lex greater so pick new one return True break return False def suffix_automata(a,b): rb = b[::-1] # reverse b rslt1 = solve(a, rb) rslt2 = solve(rb, a) rslt = None if len(rslt1) > len(rslt2): rslt = rslt1 elif len(rslt1) < len(rslt2): rslt = rslt2 else: rslt= rslt1 if rslt1 < rslt2 else rslt2 if len(rslt) == 0: return '-1' return rslt def process_helper(a,b): return suffix_automata(a,b) for _ in range(int(input())): a = input() b = input() print(process_helper(a,b)) Other Solutions HackerRank Build a String Problem Solution HackerRank Gridland Provinces Problem Solution c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython