HackerRank Build a Palindrome problem solution YASH PAL, 31 July 2024 In this HackerRank Build a Palindrome problem solution we have given two strings a and b and we need to find a string so that string is equal to the addition of substrings of a and b means we need to find and print a string on a new line and if have more than one valid string then we need to print whichever one comes first alphabetically and if there is no valid answer then print -1 instead. Problem solution in Python. 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)) {“mode”:”full”,”isActive”:false} Problem solution in Java. import java.io.*; import java.util.*; 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(); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #include <bits/stdc++.h> #ifndef SUFFIXARRAY_H_INCLUDED #define SUFFIXARRAY_H_INCLUDED class suffix_array { public: std::vector<int> suftab[2]; std::vector<int> order; std::vector<int> sufarr; std::vector<int> bucket_count, bucket_size; std::vector<int> lcp; // lcp(sa[i], sa[i+1]) == sa.lcp[i] template<class T> void build_sa(T S[], int N) { suftab[0].resize(N); suftab[1].resize(N); order.resize(N); sufarr.resize(N); bucket_count.resize(N+1); bucket_size.resize(N+1); for(int i=0; i<N; i++) order[i]=S[i]; std::sort(order.begin(), order.end()); for(int i=0; i<N; i++) suftab[0][i]=std::lower_bound(order.begin(), order.end(), S[i])-order.begin(); int lg=0; while((1<<lg)<N) lg++; int row=0; for(int hlen=1; hlen<(1<<lg); hlen*=2, row^=1) { bucket_count.assign(N+1, 0); int pos=0; for(int i=0; i+hlen<N; i++) bucket_count[suftab[row][i+hlen]+1]++; for(int i=N-hlen; i<N; i++) order[pos++]=i; bucket_count[0]=pos; std::partial_sum(bucket_count.begin(), bucket_count.end(), bucket_size.begin()); for(int i=0; i+hlen<N; i++) order[bucket_size[suftab[row][i+hlen]]++]=i; bucket_count[0]=0; for(int i=0; i<hlen; i++) bucket_count[suftab[row][i]+1]++; std::partial_sum(bucket_count.begin(), bucket_count.end(), bucket_size.begin()); for(int i=0; i<N; i++) sufarr[bucket_size[suftab[row][order[i]]]++]=order[i]; int prev_a=-1, prev_b=-1, prev_c=-1; for(int i=0; i<N; i++) { const int x=sufarr[i]; const int now_a=suftab[row][x]; const int now_b=(x+hlen<N?suftab[row][x+hlen]:-1); prev_c+=now_a!=prev_a || now_b!=prev_b; suftab[row^1][x]=prev_c; prev_a=now_a; prev_b=now_b; } } if(row==1) suftab[0].swap(suftab[1]); } template<class T> void build(T S[], int N) { build_sa(S, N); lcp.resize(sufarr.size()); for(int i=0, len=0; i<N; i++) { if(get_rank(i)==N-1) len=0; else { int j=sufarr[get_rank(i)+1]; int maxl=N-std::max(i, j); while(len<maxl && S[i+len]==S[j+len]) len++; lcp[get_rank(i)]=len; if(len>0) len--; } } } inline int get_rank(const int& idx) const { return suftab[0][idx]; } int operator[] (const int& idx) const { return sufarr[idx]; } }; #endif // SUFFIXARRAY_H_INCLUDED const int HASH_MAXN=400001; const int X=129; const int MOD1=1000000009; const int MOD2=1000000021; int P1[HASH_MAXN]; int P2[HASH_MAXN]; struct Hash { int len, val0, val1; Hash(): len(0), val0(0), val1(0) { // } Hash(int val): len(1), val0(val), val1(val) { // } Hash operator+ (const Hash& other) const { Hash ret; ret.len=len+other.len; ret.val0=(other.val0+1LL*P1[other.len]*val0)%MOD1; ret.val1=(other.val1+1LL*P2[other.len]*val1)%MOD2; return ret; } Hash operator- (const Hash& other) const { Hash ret; ret.len=len-other.len; ret.val0=val0-1LL*P1[len-other.len]*other.val0%MOD1; if(ret.val0<0) ret.val0+=MOD1; ret.val1=val1-1LL*P2[len-other.len]*other.val1%MOD2; if(ret.val1<0) ret.val1+=MOD2; return ret; } bool operator< (const Hash& other) const { if(len!=other.len) return len<other.len; if(val0!=other.val0) return val0<other.val0; return val1<other.val1; } bool operator== (const Hash& other) const { return len==other.len && val0==other.val0 && val1==other.val1; } bool operator!= (const Hash& other) const { return !(*this==other); } }; void init_hash() { P1[0]=1; for(int i=1; i<HASH_MAXN; i++) P1[i]=1LL*P1[i-1]*X%MOD1; P2[0]=1; for(int i=1; i<HASH_MAXN; i++) P2[i]=1LL*P2[i-1]*X%MOD2; } static int _hash_initialized=(init_hash(), 0); int tlen; int msuf[200001]; Hash H[200001]; Hash R[200001]; Hash get_substr(int l, int r) { if(l==0) return H[r]; return H[r]-H[l-1]; } Hash get_r_substr(int l, int r) { if(r==tlen-1) return R[l]; return R[l]-R[r+1]; } Hash get_hash(vector<pair<int, int>>& a, int l) { Hash h; for(auto& it: a) { if(l==0) break; if(abs(it.first-it.second)+1<=l) { l-=abs(it.first-it.second)+1; if(it.first>it.second) h=h+get_r_substr(it.second, it.first); else h=h+get_substr(it.first, it.second); } else { if(it.first>it.second) h=h+get_r_substr(it.first-l+1, it.first); else h=h+get_substr(it.first, it.first+l-1); break; } } return h; } char get_char(string& t, vector<pair<int, int>>& a, int l) { for(auto& it: a) { if(abs(it.first-it.second)+1<=l) l-=abs(it.first-it.second)+1; else { if(it.first>it.second) return t[it.first-l]; return t[it.first+l]; } } return '?'; } vector<pair<int, int>> get_min(string& t, vector<pair<int, int>> a, vector<pair<int, int>> b) { int la=0, lb=0; for(auto& it: a) la+=abs(it.first-it.second)+1; for(auto& it: b) lb+=abs(it.first-it.second)+1; assert(la==lb); int lo=0, mid, hi=min(la, lb); while(lo<hi) { mid=(lo+hi+1)/2; if(get_hash(a, mid)==get_hash(b, mid)) lo=mid; else hi=mid-1; } if(lo==min(la, lb) || get_char(t, a, lo)<get_char(t, b, lo)) return a; return b; } pair<int, string> solve(string s, string t) { tlen=t.length(); reverse(s.begin(), s.end()); string S=t+'#'+s; suffix_array sa; sa.build(S.c_str(), S.length()); for(int i=0; i<=(int)t.length(); i++) msuf[i]=0; int len=0; for(int i=0; i<(int)S.length(); i++) { int suf=sa[i]; if(suf<(int)t.length()) msuf[suf]=max(msuf[suf], len); else if(suf>(int)t.length() && i+1<(int)S.length()) len=max(len, sa.lcp[i]); if(i+1<(int)S.length()) len=min(len, sa.lcp[i]); } len=0; for(int i=(int)S.length()-1; i>=0; i--) { int suf=sa[i]; if(suf<(int)t.length()) msuf[suf]=max(msuf[suf], len); else if(suf>(int)t.length() && i-1>=0) len=max(len, sa.lcp[i-1]); if(i-1>=0) len=min(len, sa.lcp[i-1]); } Hash h; for(int i=0; i<(int)t.length(); i++) { h=h+Hash(t[i]); H[i]=h; } h=Hash(); for(int i=(int)t.length()-1; i>=0; i--) { h=h+Hash(t[i]); R[i]=h; } vector<pair<int, int>> ans2; int ans=0; for(int i=0; i<(int)t.length(); i++) if(msuf[i]) { if(msuf[i]*2>ans) { ans=msuf[i]*2; ans2={{i, i+msuf[i]-1}, {i+msuf[i]-1, i}}; } else if(msuf[i]*2==ans) ans2=get_min(t, ans2, {{i, i+msuf[i]-1}, {i+msuf[i]-1, i}}); } // one center for(int i=0; i<(int)t.length(); i++) { int l=min(i+1, (int)t.length()-i); int lo=1, mid, hi=l; while(lo<hi) { mid=(lo+hi+1)/2; if(get_r_substr(i-mid+1, i)==get_substr(i, i+mid-1)) lo=mid; else hi=mid-1; } if(msuf[i+lo]) { int v=2*lo-1+2*msuf[i+lo]; if(v>ans) { ans=v; ans2={{i+lo+msuf[i+lo]-1, i+lo}, {i-lo+1, i+lo+msuf[i+lo]-1}}; } else if(v==ans) ans2=get_min(t, ans2, {{i+lo+msuf[i+lo]-1, i+lo}, {i-lo+1, i+lo+msuf[i+lo]-1}}); } } // two centers for(int i=0; i<(int)t.length()-1; i++) { int l=min(i+1, (int)t.length()-(i+1)); int lo=0, mid, hi=l; while(lo<hi) { mid=(lo+hi+1)/2; if(get_r_substr(i-mid+1, i)==get_substr(i+1, i+1+mid-1)) lo=mid; else hi=mid-1; } if(msuf[i+1+lo]) { int v=2*lo+2*msuf[i+1+lo]; if(v>ans) { ans=v; ans2={{i+1+lo+msuf[i+1+lo]-1, i+1+lo}, {i-lo+1, i+1+lo+msuf[i+1+lo]-1}}; } else if(v==ans) ans2=get_min(t, ans2, {{i+1+lo+msuf[i+1+lo]-1, i+1+lo}, {i-lo+1, i+1+lo+msuf[i+1+lo]-1}}); } } string res=""; for(auto& it: ans2) { if(it.first>it.second) { for(int i=it.first; i>=it.second; i--) res+=t[i]; } else { for(int i=it.first; i<=it.second; i++) res+=t[i]; } } return make_pair(ans, res); } string _main() { string a, b; cin>>a>>b; if(a.length()<=50 && b.length()<=50) { string ans=""; for(int la=1; la<=(int)a.length(); la++) { for(int i=0; i+la-1<(int)a.length(); i++) { for(int lb=1; lb<=(int)b.length(); lb++) { for(int j=0; j+lb-1<(int)b.length(); j++) { string s=a.substr(i, la)+b.substr(j, lb); string t=s; reverse(t.begin(), t.end()); if(s==t) { if(s.length()>ans.length()) ans=s; else if(s.length()==ans.length()) ans=min(ans, s); } } } } } if(ans.empty()) return "-1"; return ans; } auto x=solve(a, b); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); auto y=solve(b, a); reverse(y.second.begin(), y.second.end()); if(max(x.first, y.first)==0) return "-1"; if(x.first>y.first) return x.second; else if(x.first<y.first) return y.second; return min(x.second, y.second); } int main() { int Q; scanf("%d", &Q); while(Q--) cout<<_main()<<endl; return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. #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] = ' '; 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] = ' '; } 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("-1n"); } else { printf("%sn", p); } free(p); free(a); free(b); } return 0; } {“mode”:”full”,”isActive”:false} algorithm coding problems