# HackerRank Functional Palindromes problem solution

In this HackerRank Functional Palindromes problem, we have a string consisting of n lowercase letters. and we need to perform queries on it.

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;

public class Solution {

public static void iota(int v[], int end, int val) {
for (int i = 0; i < end; i++) {
v[i] = val++;
}
}

static class Tlll {
long t0;
int t1;
int t2;

Tlll(long t0, int t1, int t2) {
this.t0 = t0;
this.t1 = t1;
this.t2 = t2;
}
}

static final int AB = 26;
static final int MOD = 1_000_000_007;

static class PalindromicTree {
int left;
int len;
int sl;
long cnt;
int[] c = new int[AB];
}

static PalindromicTree[] pt;
static char[] a;
static int[] sa;
static int[] isa;

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];
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;
}
for (int i = 0; i < n; i++) {
isa[i] = h[i];
}

if (m == n) {
break;
}
}
k = 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 Tlll[] palindromicTree(int n, int x[], int seq[]) {
int allo = 2;
int u = 1;
pt[0].len = 0; pt[1].len = -1;
pt[0].sl = pt[1].sl = 1;
for (int i = 0; i < n; i++) {
while (i-pt[u].len-1 < 0 || a[i-pt[u].len-1] != a[i]) {
u = pt[u].sl;
}
char c = a[i];
if (pt[u].c[c-'a'] == 0) {
int v = allo++;
int w = pt[u].sl;
pt[v].len = pt[u].len+2;
pt[v].left = i+1-pt[v].len;
while (a[i-pt[w].len-1] != a[i]) {
w = pt[w].sl;
}
pt[v].sl = pt[w].c[c-'a'];
pt[u].c[c-'a'] = v;
}
u = pt[u].c[c-'a'];
pt[u].cnt++;
}
Arrays.fill(x, 0, n, 0);
for (int i = 2; i < allo; i++) {
x[pt[i].len-1]++;
}
for (int i = 1; i < n; i++) {
x[i] += x[i-1];
}
for (int i = 2; i < allo; i++) {
seq[--x[pt[i].len-1]] = i;
}
List<Tlll> palin = new ArrayList<>();
for (int i = allo-2; --i >= 0; ) {
u = seq[i];
pt[pt[u].sl].cnt += pt[u].cnt;
}
return palin.toArray(new Tlll[palin.size()]);
}

static int[][] tab;

static int lcp(int i, int j) {
if (i == j) {
return 500000;
}
if (i > j) {
int t = i;
i = j;
j = t;
}
int t = 63 - Long.numberOfLeadingZeros(j-i);
return Math.min(tab[t][i+1], tab[t][j+1-(1<<t)]);
}

static int lowerBound(Tlll[] arr, Tlll key) {
if (key.t0 <= arr[0].t0) {
return 0;
}
if (key.t0 > arr[arr.length - 1].t0) {
return 0;
}

int index = Arrays.binarySearch(arr, key, (x, y) -> {
if (x.t0 == y.t0) {
return 0;
}
return x.t0 > y.t0 ? 1 : -1;
} );
if (index < 0) {
index = - index - 1;
if (index < 0) {
return 0;
}
}
while (index > 0 && arr[index-1].t0 == key.t0) {
index--;
}
return index;
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());

long[] has = new long[n+1];
long[] pw = new long[n+1];

pw[0] = 1;
pt = new PalindromicTree[n+2];
for (int i = 0; i < n; i++) {
has[i+1] = (has[i]*100001+a[i]) % MOD;
pw[i+1] = pw[i]*100001 % MOD;
pt[i] = new PalindromicTree();
}
pt[n] = new PalindromicTree();
pt[n+1] = new PalindromicTree();

tab = new int[63 - Integer.numberOfLeadingZeros(n-1) + 1][n > 'z'+1 ? n : 'z'+1];
Tlll[] palin = palindromicTree(n, tab[0], tab[1]);
sa = new int[n];
isa = new int[n];
suffixArray(n, 'z'+1, tab[0], tab[1]);

for (int j = 1; 1<<j < n; j++) {
for (int i = n-(1<<j); i > 0; i--) {
tab[j][i] = Math.min(tab[j-1][i], tab[j-1][i+(1<<j-1)]);
}
}
Arrays.sort(palin, (x, y) -> {
return lcp(isa[x.t1], isa[y.t1]) >= Math.min(x.t2, y.t2)
? x.t2 - y.t2 : isa[x.t1] - isa[y.t1];
});

for (int i = 1; i < palin.length; i++) {
palin[i].t0 += palin[i-1].t0;
}
for (int i = 0; i < palin.length; i++) {
int l = palin[i].t1;
int r = palin[i].t2;
palin[i].t1 = (int)((has[l+r] - (has[l]*pw[r]) % MOD + MOD) % MOD);
}

for (int i = 0; i < q; i++) {
long k = Long.parseLong(st.nextToken());
if (k > palin[palin.length-1].t0) {
bw.write("-1\n");
} else {
int it = lowerBound(palin, new Tlll(k, 0, 0));
bw.write(palin[it].t1 + "\n");
}
}

bw.newLine();
bw.close();
br.close();
}
}```

## Problem solution in C++ programming.

```#include <bits/stdc++.h>
using namespace std ;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int MAXN = 105000;

struct node {
int next[26];
int len;
int num, l, r;
};

int len;
char s[MAXN];
node tree[MAXN];
int num;
int suff;
long long ans;
viii A;
int n, q;
int cur = suff, curlen = 0;
int let = s[pos] - 'a';

while (true) {
curlen = tree[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
break;
}
if (tree[cur].next[let]) {
suff = tree[cur].next[let];
tree[suff].num ++;
return false;
}

num++;
suff = num;
tree[num].len = tree[cur].len + 2;
tree[num].r = pos;
tree[num].l = pos - tree[num].len + 1;
tree[cur].next[let] = num;
if (tree[num].len == 1) {
tree[num].num = 1;
return true;
}

tree[num].num ++;
while (true) {
curlen = tree[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
break;
}
}
return true;
}

void initTree() {
num = 2; suff = 2;
tree[1].len = -1; tree[1].sufflink = 1;
tree[2].len = 0; tree[2].sufflink = 1;
tree[1].num = tree[2].num = 0;
}

void dfs( int u ) {
for( auto it: adj[u] ) {
dfs(it);
tree[u].num += tree[it].num;
}
}

int iSA[MAXN], SA[MAXN];
int cnt[MAXN], next_gen[MAXN], lcp[ MAXN ], LCP[MAXN][22]; //internal
bool bh[MAXN], b2h[MAXN],m_arr[MAXN];

bool smaller_first_char(int a, int b){
return s[a] < s[b];
}

void SuffixSort(int n) {
for (int i=0; i<n; ++i){
SA[i] = i;
}
sort(SA, SA + n, smaller_first_char);
for (int i=0; i<n; ++i){
bh[i] = i == 0 || s[SA[i]] != s[SA[i-1]];
b2h[i] = false;
}
for (int h = 1; h < n; h <<= 1){
int buckets = 0;
for (int i=0, j; i < n; i = j){
j = i + 1;
while (j < n && !bh[j]) j++;
next_gen[i] = j;
buckets++;
}
if (buckets == n) break;
for (int i = 0; i < n; i = next_gen[i]){
cnt[i] = 0;
for (int j = i; j < next_gen[i]; ++j){
iSA[SA[j]] = i;
}
}
cnt[iSA[n - h]]++;
b2h[iSA[n - h]] = true;
for (int i = 0; i < n; i = next_gen[i]){
for (int j = i; j < next_gen[i]; ++j){
int s = SA[j] - h;
if (s >= 0){
b2h[iSA[s]] = true;
}
}
for (int j = i; j < next_gen[i]; ++j){
int s = SA[j] - h;
if (s >= 0 && b2h[iSA[s]]){
for (int k = iSA[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false;
}
}
}
for (int i=0; i<n; ++i){
SA[iSA[i]] = i;
bh[i] |= b2h[i];
}
}
for (int i=0; i<n; ++i){
iSA[SA[i]] = i;
}
}

void InitLCP(int n) {
for (int i=0; i<n; ++i)
iSA[SA[i]] = i;
lcp[0] = 0;
for (int i=0, h=0; i<n; ++i) {
if (iSA[i] > 0) {
int j = SA[iSA[i]-1];
while (i + h < n && j + h < n && s[i+h] == s[j+h])
h++;
lcp[iSA[i]] = h;
if (h > 0)
h--;
}
}
}

void ConstructLCP() {
InitLCP( len );
for(int i = 0;i<len;++i)
LCP[i][0] = lcp[i];
for(int j = 1;(1<<j)<=len;++j){
for(int i = 0;i+(1<<j)-1<len;++i){
if(LCP[i][j-1]<=LCP[i+ ( 1<<(j-1) )][j-1])
LCP[i][j] = LCP[i][j-1];
else
LCP[i][j] = LCP[i+(1<<(j-1))][j-1];
}
}
}

int GetLCP(int x, int y) {
if(x == y) return len-SA[x];
if(x > y) swap(x,y);
int log = 0;
while((1<<log)<=(y-x)) ++log;
--log;
return min(LCP[x+1][log],LCP[y-(1<<log)+1][log]);
}

bool cmp(const piii &a, const piii &b) {
int l1, r1, l2, r2, len1, len2;
l1 = a.ft.ft;
r1 = a.ft.sd;
l2 = b.ft.ft;
r2 = b.ft.sd;
len1 = r1 - l1 + 1;
len2 = r2 - l2 + 1;
int res = 0;
int v = GetLCP(iSA[l1], iSA[l2]);
if(v >= min(len1, len2)) {
res = (len1 < len2);
} else {
res = (iSA[l1] < iSA[l2]);
}
return res;
}

int P[MAXN], HashF[MAXN], HashR[MAXN];
class RollingHash {
public:
RollingHash() {
prime = 100001;
mod1 = 1000000007;
mod2 = 1897266401;
P[0] = 1;
for(int i=1; i<MAXN; i++) {
P[i] = 1LL * P[i-1] * prime % mod1;
}
}

void Construct() {
HashF[0] = HashR[ len+1 ] = 0;
for(int i=1; i<=len; i++) {
HashF[i] = ( 1LL * HashF[i-1] * prime + s[i-1] ) % mod1;
HashR[len-i+1] = ( 1LL * HashR[len-i+2] * prime + s[ len - i ] ) % mod1;
}
}

int GetForwardHash( int l, int r ) {
if( l == 1 ) return HashF[r];
int hash = HashF[r] - 1LL * HashF[l-1] * P[ r - l + 1 ] % mod1;
if( hash < 0 ) hash += mod1;
return hash;
}
int GetBackwardHash( int l, int r ) {
if( r == len ) return HashR[l];
int hash = HashR[l] - 1LL * HashR[r+1] * P[ r - l + 1 ] % mod1;
if( hash < 0 ) hash += mod1;
return hash;
}
bool IsPalin( int l, int r ) {
if( r < l ) return true;
return (GetForwardHash(l, r) == GetBackwardHash(l, r));
}

private:
int prime, mod1, mod2;
};

int main() {

cin >> n >> q;
cin >> s;
len = n;

initTree();
SuffixSort( len );
ConstructLCP();
for (int i = 0; i < len; i++) {
}

for(int i=2; i<=num; i++) {
}

dfs(1);

for(int i=3; i<=num; i++) {
A.pb(mp(mp(tree[i].l, tree[i].r), tree[i].num));
}

sort(all(A), cmp);
vl bs, has;
RollingHash obj;
obj.Construct();
ll v = 0;
for( auto it: A ) {
v += it.sd;
bs.pb( v );
has.pb(obj.GetForwardHash(it.ft.ft+1, it.ft.sd+1));
}
ll k;
while( q-- ) {
cin >> k;
if( k > v ) cout << -1 << "\n";
else {
auto it = lower_bound(all(bs), k);
cout << has[it-bs.begin()] << "\n";
}
}
return 0;
}```

## Problem solution in C programming.

```#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#define MAX 400005
#define MOD 1000000007
const int A = 100001;
struct Node
{
int To[26], fail, len, cnt, l, r;
}T[MAX];
long long Sum[MAX];
char S[MAX];
int Has[MAX], Pre[MAX], Len[MAX], Ref[MAX], dfn_cnt, tot, cnt, L, Lst;
void Pre_Treat()
{
cnt = 1;
T[1].len = -1;
T[0].fail = 1;
}
int Get(int p, int x)
{
for( ; S[L - T[p].len - 1] != x ; p = T[p].fail );
return p;
}
{
S[++L] = x;
int cur = Get(Lst, x);
if(!T[cur].To[x])
{
++cnt;
T[cnt].len = T[cur].len + 2;
T[cnt].fail = T[Get(T[cur].fail, x)].To[x];
T[cur].To[x] = cnt;
}
Lst = T[cur].To[x];
}
int Gethas(int l, int r)
{
return ( Pre[r] - Pre[l-1] * 1ll * Len[r-l+1] % MOD + MOD ) % MOD;
}
bool Same(int l, int r, int u, int v)
{
return Gethas(l, r) == Gethas(u, v);
}
int min(int p, int q)
{
return p < q ? p : q;
}
int comp(const void *a, const void *b)
{
int c = 1, d = min(T[*(int*)a].len, T[*(int*)b].len), tmp = 0;
for( int mid ; c <= d ; )
{
mid = c + d >> 1;
if(Same(T[*(int*)a].l, T[*(int*)a].l + mid - 1, T[*(int*)b].l, T[*(int*)b].l + mid - 1))
{
tmp = mid, c = mid + 1;
}
else
{
d = mid - 1;
}
}
if( tmp == min(T[*(int*)a].len, T[*(int*)b].len) )
{
return T[*(int*)a].len - T[*(int*)b].len;
}
return S[T[*(int*)a].l + tmp] - S[T[*(int*)b].l + tmp];
}
int main()
{
static char ch[100005];
Pre_Treat();
S[0] = -1;
int n, q;
scanf("%d%d", &n, &q);
scanf("%s", ch + 1);
Len[0] = 1;
for( int i = 1 ; i <= n ; i++ )
{
Len[i] = Len[i-1] * 1ll * A % MOD;
Pre[i] = ( Pre[i-1] * 1ll * A % MOD + ch[i] ) % MOD;
T[Lst].r = i, T[Lst].l = i - T[Lst].len + 1;
T[Lst].cnt++;
Has[Lst] = Gethas(i - T[Lst].len + 1, i);
}
for( int i = 2 ; i <= cnt ; i++ )
{
Ref[i-1] = i;
}
for( int i = cnt ; i ; i-- )
{
T[T[i].fail].cnt += T[i].cnt;
}
qsort(Ref, cnt, sizeof(int), comp);
for( int i = 1 ; i < cnt ; i++ )
{
Sum[i] = Sum[i - 1] + T[Ref[i]].cnt;
}
for( ; q ; q-- )
{
long long k;
scanf("%lld", &k);
int l = 1, r = cnt - 1, tmp = cnt;
for( int mid ; l <= r ; )
{
mid = l + r >> 1;
if( Sum[mid] >= k )
{
tmp = mid, r = mid - 1;
}
else
{
l = mid + 1;
}
}
if( tmp == cnt )
{
printf("-1\n");
}
else
{
printf("%d\n", Has[Ref[tmp]]);
}
}
return 0;
}```