Build a Palindrome – HackerRank Solution

In this post, we will solve Build a Palindrome HackerRank Solution. This problem (Build a Palindrome) is a part of HackerRank Problem Solving series.

Contents

Solution – Build a Palindrome – HackerRank Solution

C++

#include <bits/stdc++.h>

using namespace std;

#ifndef SUFFIXARRAY_H_INCLUDED
#define SUFFIXARRAY_H_INCLUDED

#include <algorithm>
#include <vector>

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

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))

Java

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class F3 {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        for(int T = ni();T > 0;T--){
            char[] s = ns().toCharArray();
            char[] t = ns().toCharArray();
            
            String b1 = go(s, t);
//            tr(best);
            char[] rs = rev(s);
            char[] rt = rev(t);
            String b2 = go(rt, rs);
            
            if(b1 == null && b2 == null){
                out.println(-1);
            }else if(b1 == null){
                out.println(b2);
            }else if(b2 == null){
                out.println(b1);
            }else if(b1.length() > b2.length() || b1.length() == b2.length() && b1.compareTo(b2) < 0){
                out.println(b1);
            }else{
                out.println(b2);
            }
        }
    }
    
    public static char[] rev(char[] a)
    {
        for(int i = 0, j = a.length-1;i < j;i++,j--){
            char c = a[i]; a[i] = a[j]; a[j] = c;
        }
        return a;
    }
    
    String go(char[] s, char[] t)
    {
        char[] st = new char[s.length+t.length];
        for(int i = 0;i < s.length;i++)st[i] = s[s.length-1-i];
        for(int i = 0;i < t.length;i++)st[i+s.length] = t[i];
        
//        String S = new String(s);
//        String ST = new String(st);
        int[] sa = sa(st);
        int nn = s.length+t.length;
        int[] isa = new int[nn];
        for(int i = 0;i < nn;i++)isa[sa[i]] = i;
        int[] lcp = buildLCP(st, sa);
//        tr(st);
//        tr(sa);
        
        int[] llcp = new int[nn];
        {
            int cur = 0;
            for(int i = 0;i < nn;i++){
                if(sa[i] < s.length){
                    llcp[s.length-1-sa[i]] = cur;
                }else{
                    cur = 9999999;
                }
                if(i+1 < nn)cur = Math.min(cur, lcp[i+1]);
            }
        }
        int[] rlcp = new int[nn];
        {
            int cur = 0;
            for(int i = nn-1;i >= 0;i--){
                if(sa[i] < s.length){
                    rlcp[s.length-1-sa[i]] = cur;
                }else{
                    cur = 9999999;
                }
                cur = Math.min(cur, lcp[i]);
            }
        }
//        tr(llcp, rlcp);
        int[] rad = palindrome(s);
//        tr("s", new String(s));
//        tr(rad);
        
        int[] pals = new int[s.length];
        
        {
            int[][] es = new int[s.length*2-1][];
            for(int i = 0;i < s.length*2-1;i++){
                es[i] = new int[]{(i-rad[i]+1)/2, rad[i]};
            }
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    return a[0] - b[0];
                }
            });
            int p = 0;
            int cur = 0;
            for(int i = 0;i < s.length;i++){
                while(p < es.length && es[p][0] <= i){
                    cur = Math.max(cur, es[p][1]);
                    p++;
                }
                pals[i] = Math.max(pals[i], cur);
                cur = Math.max(cur-2, 0);
            }
        }
//        tr("pals", pals);
        
        char[] srs = new char[s.length*2];
        for(int i = 0;i < s.length;i++){
            srs[i] = srs[s.length*2-1-i] = s[i];
        }
        int[] ssa = sa(srs);
        int[] issa = new int[srs.length];
        for(int i = 0;i < srs.length;i++)issa[ssa[i]] = i;
        int[] slcp = buildLCP(srs, ssa);
        SegmentTreeRMQ sts = new SegmentTreeRMQ(slcp);
        
        int maxlen = 0;
        int[] lbest = null;
        for(int start = 0;start < s.length;start++){
            int xlcp = Math.min(start+1, Math.max(llcp[start], rlcp[start]));
            if(xlcp == 0)continue;
            int lpal = start+1 < s.length ? pals[start+1] : 0;
//            tr(start, xlcp, lpal);
            int len = lpal+xlcp*2;
            if(len > maxlen){
                maxlen = len;
                lbest = new int[]{start-xlcp+1, start+lpal+1, s.length-1-start+s.length, s.length-1-(start-xlcp+1)+1+s.length};
            }else if(len == maxlen){
                int[] can = new int[]{start-xlcp+1, start+lpal+1, s.length-1-start+s.length, s.length-1-(start-xlcp+1)+1+s.length};
                int ulcp = sts.minx(Math.min(issa[can[0]], issa[lbest[0]])+1, Math.max(issa[can[0]], issa[lbest[0]])+1);
                if(ulcp < can[1]-can[0] && ulcp < lbest[1]-lbest[0]){
                    if(issa[can[0]] < issa[lbest[0]]){
                        lbest = can;
                    }
                    continue;
                }
                int L = can[1]-can[0];
                int R = lbest[1]-lbest[0];
                if(L < R){
                    int lpos = can[2], rpos = lbest[0]+L;
                    ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
                    if(ulcp < R-L){
                        if(issa[lpos] < issa[rpos]){
                            lbest = can;
                        }
                        continue;
                    }
                    
                    lpos = can[2] + R-L; rpos = lbest[2];
                    ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
                    if(issa[lpos] < issa[rpos]){
                        lbest = can;
                    }
                }else{
                    int lpos = can[0]+R, rpos = lbest[2];
                    ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
                    if(ulcp < L-R){
                        if(issa[lpos] < issa[rpos]){
                            lbest = can;
                        }
                        continue;
                    }
                    
                    lpos = can[2]; rpos = lbest[2]+L-R;
                    ulcp = sts.minx(Math.min(issa[lpos], issa[rpos])+1, Math.max(issa[lpos], issa[rpos])+1);
                    if(issa[lpos] < issa[rpos]){
                        lbest = can;
                    }
                }
            }
        }
        
        if(lbest == null){
            return null;
        }else{
            StringBuilder sb = new StringBuilder();
            for(int i = lbest[0];i < lbest[1];i++)sb.append(srs[i]);
            for(int i = lbest[2];i < lbest[3];i++)sb.append(srs[i]);
            return sb.toString();
        }
    }
    
    public static class SegmentTreeRMQ {
        public int M, H, N;
        public int[] st;
        
        public SegmentTreeRMQ(int n)
        {
            N = n;
            M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
            H = M>>>1;
            st = new int[M];
            Arrays.fill(st, 0, M, Integer.MAX_VALUE);
        }
        
        public SegmentTreeRMQ(int[] a)
        {
            N = a.length;
            M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
            H = M>>>1;
            st = new int[M];
            for(int i = 0;i < N;i++){
                st[H+i] = a[i];
            }
            Arrays.fill(st, H+N, M, Integer.MAX_VALUE);
            for(int i = H-1;i >= 1;i--)propagate(i);
        }
        
        public void update(int pos, int x)
        {
            st[H+pos] = x;
            for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
        }
        
        private void propagate(int i)
        {
            st[i] = Math.min(st[2*i], st[2*i+1]);
        }
        
        public int minx(int l, int r){
            if(l >= r)return 0;
            int min = Integer.MAX_VALUE;
            while(l != 0){
                int f = l&-l;
                if(l+f > r)break;
                int v = st[(H+l)/f];
                if(v < min)min = v;
                l += f;
            }
            
            while(l < r){
                int f = r&-r;
                int v = st[(H+r)/f-1];
                if(v < min)min = v;
                r -= f;
            }
            return min;
        }
        
        public int min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
        
        private int min(int l, int r, int cl, int cr, int cur)
        {
            if(l <= cl && cr <= r){
                return st[cur];
            }else{
                int mid = cl+cr>>>1;
                int ret = Integer.MAX_VALUE;
                if(cl < r && l < mid){
                    ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
                }
                if(mid < r && l < cr){
                    ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
                }
                return ret;
            }
        }
        
        public int firstle(int l, int v) {
            int cur = H+l;
            while(true){
                if(st[cur] <= v){
                    if(cur < H){
                        cur = 2*cur;
                    }else{
                        return cur-H;
                    }
                }else{
                    cur++;
                    if((cur&cur-1) == 0)return -1;
                    if((cur&1)==0)cur>>>=1;
                }
            }
        }
        
        public int lastle(int l, int v) {
            int cur = H+l;
            while(true){
                if(st[cur] <= v){
                    if(cur < H){
                        cur = 2*cur+1;
                    }else{
                        return cur-H;
                    }
                }else{
                    if((cur&cur-1) == 0)return -1;
                    cur--;
                    if((cur&1)==1)cur>>>=1;
                }
            }
        }
    }

    
    public static int[] palindrome(char[] str)
    {
        int n = str.length;
        int[] r = new int[2*n];
        int k = 0;
        for(int i = 0, j = 0;i < 2*n;i += k, j = Math.max(j-k, 0)){
            // normally
            while(i-j >= 0 && i+j+1 < 2*n && str[(i-j)/2] == str[(i+j+1)/2])j++;
            r[i] = j;
            
            // skip based on the theorem
            for(k = 1;i-k >= 0 && r[i]-k >= 0 && r[i-k] != r[i]-k;k++){
                r[i+k] = Math.min(r[i-k], r[i]-k);
            }
        }
        return r;
    }

    
    private static interface BaseArray {
        public int get(int i);

        public void set(int i, int val);

        public int update(int i, int val);
    }

    private static class CharArray implements BaseArray {
        private char[] m_A = null;
        private int m_pos = 0;

        CharArray(char[] A, int pos) {
            m_A = A;
            m_pos = pos;
        }

        public int get(int i) {
            return m_A[m_pos + i] & 0xffff;
        }

        public void set(int i, int val) {
            m_A[m_pos + i] = (char) (val & 0xffff);
        }

        public int update(int i, int val) {
            return m_A[m_pos + i] += val & 0xffff;
        }
    }

    private static class IntArray implements BaseArray {
        private int[] m_A = null;
        private int m_pos = 0;

        IntArray(int[] A, int pos) {
            m_A = A;
            m_pos = pos;
        }

        public int get(int i) {
            return m_A[m_pos + i];
        }

        public void set(int i, int val) {
            m_A[m_pos + i] = val;
        }

        public int update(int i, int val) {
            return m_A[m_pos + i] += val;
        }
    }

    /* find the start or end of each bucket */
    private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
        int i;
        for(i = 0;i < k;++i){
            C.set(i, 0);
        }
        for(i = 0;i < n;++i){
            C.update(T.get(i), 1);
        }
    }

    private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
        int i, sum = 0;
        if(end != false){
            for(i = 0;i < k;++i){
                sum += C.get(i);
                B.set(i, sum);
            }
        }else{
            for(i = 0;i < k;++i){
                sum += C.get(i);
                B.set(i, sum - C.get(i));
            }
        }
    }

    /* sort all type LMS suffixes */
    private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
            BaseArray B, int n, int k) {
        int b, i, j;
        int c0, c1;
        /* compute SAl */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B.get(c1 = T.get(j));
        --j;
        SA[b++] = (T.get(j) < c1) ? ~j : j;
        for(i = 0;i < n;++i){
            if(0 < (j = SA[i])){
                if((c0 = T.get(j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                --j;
                SA[b++] = (T.get(j) < c1) ? ~j : j;
                SA[i] = 0;
            }else if(j < 0){
                SA[i] = ~j;
            }
        }
        /* compute SAs */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, true); /* find ends of buckets */
        for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
            if(0 < (j = SA[i])){
                if((c0 = T.get(j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                --j;
                SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
                SA[i] = 0;
            }
        }
    }

    private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
        int i, j, p, q, plen, qlen, name;
        int c0, c1;
        boolean diff;

        /*
         * compact all the sorted substrings into the first m items of SA 2*m
         * must be not larger than n (proveable)
         */
        for(i = 0;(p = SA[i]) < 0;++i){
            SA[i] = ~p;
        }
        if(i < m){
            for(j = i, ++i;;++i){
                if((p = SA[i]) < 0){
                    SA[j++] = ~p;
                    SA[i] = 0;
                    if(j == m){
                        break;
                    }
                }
            }
        }

        /* store the length of all substrings */
        i = n - 1;
        j = n - 1;
        c0 = T.get(n - 1);
        do{
            c1 = c0;
        }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
        for(;0 <= i;){
            do{
                c1 = c0;
            }while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
            if(0 <= i){
                SA[m + ((i + 1) >> 1)] = j - i;
                j = i + 1;
                do{
                    c1 = c0;
                }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
            }
        }

        /* find the lexicographic names of all substrings */
        for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
            p = SA[i];
            plen = SA[m + (p >> 1)];
            diff = true;
            if((plen == qlen) && ((q + plen) < n)){
                for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
                }
                if(j == plen){
                    diff = false;
                }
            }
            if(diff != false){
                ++name;
                q = p;
                qlen = plen;
            }
            SA[m + (p >> 1)] = name;
        }

        return name;
    }

    /* compute SA and BWT */
    private static void induceSA(BaseArray T, int[] SA, BaseArray C,
            BaseArray B, int n, int k) {
        int b, i, j;
        int c0, c1;
        /* compute SAl */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B.get(c1 = T.get(j));
        SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
        for(i = 0;i < n;++i){
            j = SA[i];
            SA[i] = ~j;
            if(0 < j){
                if((c0 = T.get(--j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
            }
        }
        /* compute SAs */
        if(C == B){
            getCounts(T, C, n, k);
        }
        getBuckets(C, B, k, true); /* find ends of buckets */
        for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
            if(0 < (j = SA[i])){
                if((c0 = T.get(--j)) != c1){
                    B.set(c1, b);
                    b = B.get(c1 = c0);
                }
                SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
            }else{
                SA[i] = ~j;
            }
        }
    }

    /*
     * find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
     * (excluding T and SA) of at most 2n+O(1) for a constant alphabet
     */
    private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
        BaseArray C, B, RA;
        int i, j, b, m, p, q, name, newfs;
        int c0, c1;
        int flags = 0;

        if(k <= 256){
            C = new IntArray(new int[k], 0);
            if(k <= fs){
                B = new IntArray(SA, n + fs - k);
                flags = 1;
            }else{
                B = new IntArray(new int[k], 0);
                flags = 3;
            }
        }else if(k <= fs){
            C = new IntArray(SA, n + fs - k);
            if(k <= (fs - k)){
                B = new IntArray(SA, n + fs - k * 2);
                flags = 0;
            }else if(k <= 1024){
                B = new IntArray(new int[k], 0);
                flags = 2;
            }else{
                B = C;
                flags = 8;
            }
        }else{
            C = B = new IntArray(new int[k], 0);
            flags = 4 | 8;
        }

        /*
         * stage 1: reduce the problem by at least 1/2 sort all the
         * LMS-substrings
         */
        getCounts(T, C, n, k);
        getBuckets(C, B, k, true); /* find ends of buckets */
        for(i = 0;i < n;++i){
            SA[i] = 0;
        }
        b = -1;
        i = n - 1;
        j = n;
        m = 0;
        c0 = T.get(n - 1);
        do{
            c1 = c0;
        }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
        for(;0 <= i;){
            do{
                c1 = c0;
            }while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
            if(0 <= i){
                if(0 <= b){
                    SA[b] = j;
                }
                b = B.update(c1, -1);
                j = i;
                ++m;
                do{
                    c1 = c0;
                }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
            }
        }
        if(1 < m){
            LMSsort(T, SA, C, B, n, k);
            name = LMSpostproc(T, SA, n, m);
        }else if(m == 1){
            SA[b] = j + 1;
            name = 1;
        }else{
            name = 0;
        }

        /*
         * stage 2: solve the reduced problem recurse if names are not yet
         * unique
         */
        if(name < m){
            if((flags & 4) != 0){
                C = null;
                B = null;
            }
            if((flags & 2) != 0){
                B = null;
            }
            newfs = (n + fs) - (m * 2);
            if((flags & (1 | 4 | 8)) == 0){
                if((k + name) <= newfs){
                    newfs -= k;
                }else{
                    flags |= 8;
                }
            }
            for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
                if(SA[i] != 0){
                    SA[j--] = SA[i] - 1;
                }
            }
            RA = new IntArray(SA, m + newfs);
            SA_IS(RA, SA, newfs, m, name);
            RA = null;

            i = n - 1;
            j = m * 2 - 1;
            c0 = T.get(n - 1);
            do{
                c1 = c0;
            }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
            for(;0 <= i;){
                do{
                    c1 = c0;
                }while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
                if(0 <= i){
                    SA[j--] = i + 1;
                    do{
                        c1 = c0;
                    }while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
                }
            }

            for(i = 0;i < m;++i){
                SA[i] = SA[m + SA[i]];
            }
            if((flags & 4) != 0){
                C = B = new IntArray(new int[k], 0);
            }
            if((flags & 2) != 0){
                B = new IntArray(new int[k], 0);
            }
        }

        /* stage 3: induce the result for the original problem */
        if((flags & 8) != 0){
            getCounts(T, C, n, k);
        }
        /* put all left-most S characters into their buckets */
        if(1 < m){
            getBuckets(C, B, k, true); /* find ends of buckets */
            i = m - 1;
            j = n;
            p = SA[m - 1];
            c1 = T.get(p);
            do{
                q = B.get(c0 = c1);
                while (q < j){
                    SA[--j] = 0;
                }
                do{
                    SA[--j] = p;
                    if(--i < 0){
                        break;
                    }
                    p = SA[i];
                }while ((c1 = T.get(p)) == c0);
            }while (0 <= i);
            while (0 < j){
                SA[--j] = 0;
            }
        }
        induceSA(T, SA, C, B, n, k);
        C = null;
        B = null;
    }

    /* char */
    public static void suffixsort(char[] T, int[] SA, int n) {
        if((T == null) || (SA == null) || (T.length < n) || (SA.length < n)){
            return;
        }
        if(n <= 1){
            if(n == 1){
                SA[0] = 0;
            }
            return;
        }
        SA_IS(new CharArray(T, 0), SA, 0, n, 128);
    }
    
    public static int[] sa(char[] T)
    {
        int n = T.length;
        int[] sa = new int[n];
        suffixsort(T, sa, n);
        return sa;
    }
    
    public static int[] buildLCP(char[] str, int[] sa)
    {
        int n = str.length;
        int h = 0;
        int[] lcp = new int[n];
        int[] isa = new int[n];
        for(int i = 0;i < n;i++)isa[sa[i]] = i;
        for(int i = 0;i < n;i++){
            if(isa[i] > 0){
                for(int j = sa[isa[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
                lcp[isa[i]] = h;
            }else{
                lcp[isa[i]] = 0;
            }
            if(h > 0)h--;
        }
        return lcp;
    }

    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new F3().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Note: This problem (Build a Palindrome) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

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