[Solved] Functional Palindromes solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Algorithm

Problem Name: Data Structures - Functional Palindromes

Problem Link: https://www.hackerrank.com/challenges/functional-palindromes/problem?isFullScreen=true

In this HackerRank in Data Structures - Functional Palindromes solutions

Let's define a function, f, on a string, p of length l as follows:

f(p) = (p1 * a*l-1 + p2 * a*l-2 + ... + pl * a**0) mod m

where pi , denotes the ASCII value of the i**th character in string p,a = 100001, and m = 10**9 + 7

Nikita has a string, s, consisting of n lowercase letters that she wants to perform q queries on. Each query consists of an integer, k, and you have to find the value of f(wk) where wk) is the k**th alphabetically smallest palindromic substring of s. wk doesn't exist, print -1 instead.

Input Format

The first line contains 2 space-separated integers describing the respective values of n (the length of string s) and q (the number of queries).
The second line contains a single string denoting s .

Each of the q subsequent lines contains a single integer denoting the value of k for a query.

Constraints

1 <= n,q <= 10**5
1 <= k <= n(n+1)/2
It is guaranteed that string s consists of lowercase English alphabetic letters only (i.e., a to z)
a = 10**5 + 1
m = 10**9 + 7

Scoring

1 <= n,q <= 10**3 for 25% of the test cases.
1 <= n,q <= 10** f5or 100% of the test cases.

Output Format

For each query, print the value of function f(wk) where wk is the k**th alphabetically smallest palindromic substring of s; if wk doesn't exist, print -1 instead.

Sample Input

5 7
abcba
1
2
3
4
6
7
8

Sample Output

Code Examples

#1 Code Example with C Programming

Code - 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;
}
void Add(int x)
{
    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;
        Add(ch[i]-'a');
        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;
}

Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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, int>
#define piii pair
#define viii vector<pair >
#define vl vector<ll>
#define vll vector<pair >
#define pll pair
#define pli pair
#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 sufflink;
    int num, l, r;
};

int len;
char s[MAXN];
node tree[MAXN]; 
int num;            
int suff;           
long long ans;
vi adj[ MAXN ];
viii A;
int n, q;
bool addLetter(int pos) {
    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;  
        cur = tree[cur].sufflink;
    }       
    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].sufflink = 2;
        tree[num].num = 1;
        return true;
    }

    tree[num].num ++;
    while (true) {
        cur = tree[cur].sufflink;
        curlen = tree[cur].len;
        if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
            tree[num].sufflink = tree[cur].next[let];
            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){
          int head = iSA[s];
          iSA[s] = head + cnt[head]++;
          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++) {
        addLetter(i);
    }

    for(int i = 2; i  < = num; i++) {
        adj[tree[i].sufflink].pb(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;
}

Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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];
      palin.add(new Tlll(pt[u].cnt, pt[u].left, pt[u].len));
      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 {
    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 n = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    a = br.readLine().toCharArray();
    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++) {
      st = new StringTokenizer(br.readLine());
      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();
  }
}

Copy The Code & Try With Live Editor

Demonstration

Previous
[Solved] Pair Sums solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Next
[Solved] Lazy White Falcon solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Try With Live Editor

Category - Hacker Rank Online Judge Maniruzzaman Akash 1 year ago 387 0