In this post, we will solve Build a Palindrome HackerRank Solution. This problem (Build a Palindrome) is a part of HackerRank Problem Solving series.
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.