Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Palindromic Border Problem Solution

Yashwant Parihar, May 2, 2023May 2, 2023

In this post, we will solve HackerRank Palindromic Border Problem Solution.

A border of a string is a proper prefix of it that is also a suffix. For example:

a and abra are borders of abracadabra,
⚫ kan and kankan are borders of kankankan.
⚫de is a border of decode.
Note that decode is not a border of decode because it’s not proper.
A palindromic border is a border that is palindromic. For example,
⚫a and ana are palindromic borders of anabanana,
⚫l, lol and lolol are palindromic borders of lololol.
Let’s define P (s) as the number of palindromic borders of string s. For example, if 8 = lololol, then P(s) = 3.
Now, a string of length N has exactly N(N+1)/2 non-empty substrings (we count
substrings as distinct if they are of different lengths or are in different positions, even if they are the same string). Given a string s, consisting only of the first 8 lowercase letters of the English alphabet, your task is to find the sum of P (s’) for all the non-empty substrings s’ of s. In other words, you need to find:

where si…; is the substring of s starting at position & and ending at position j.
Since the answer can be very large, output the answer modulo 10 power 9 +7.
Input Format
The first line contains a string consisting of N characters.
Output Format
Print a single integer: the remainder of the division of the resulting number by 10 power 9 +7.

Sample Input 1

ababa

Sample Output 1

5

Sample Input 2

aaaa

Sample Output 2

10

Sample Input 3

abcacb

Sample Output 3

3

Explanation
S = ababa has 15 substrings but only 4 substrings have palindromic borders.
S1…3 aba P (S1…3)=1
S1…5 ababa P (S1…5) = 2
S2…4 bab P (S2…4) = 1
S3…5 aba P(S3…5)=1

HackerRank Palindromic Border Problem Solution
HackerRank Palindromic Border Problem Solution

Palindromic Border C Solution

#include<stdio.h>
#include<stdlib.h>
typedef long long ll;
int ri()
{
    int x;
    scanf("%d", &x);
    return x;
}
#define N 100000
char a[N+1];
struct Node
{ 
    int suff, l, c[26], cnt;
}b[N+2];
int getSuff(int i, int x)
{
    while( i - 1 - b[x].l < 0 || a[i-1-b[x].l] != a[i] )
        x = b[x].suff;
    return x;
}
int main()
{
    b[0].suff = 1;
    b[0].l = 0;
    b[1].suff = 1;
    b[1].l = -1;
    scanf("%s", a);
    int x = 1, y = 2, i;
    for( i = 0 ; a[i] ; i++ )
    {
        x = getSuff(i, x);
        if(!b[x].c[a[i]-'a'])
        {
            b[y].l = b[x].l + 2;
            b[y].suff = b[getSuff(i, b[x].suff)].c[a[i]-'a'];
            b[y].cnt = 0;
            b[x].c[a[i]-'a'] = y++;
        }
        x = b[x].c[a[i]-'a'];
        b[x].cnt++;
    }
    for( i = y ; --i >= 0 ; )
        b[b[i].suff].cnt += b[i].cnt;
    ll ans = 0;
    for( i = 2 ; i < y ; i++ )
    {
        int c = b[i].cnt;
        ans += (ll)( c - 1 ) * c / 2;
    }
    printf("%lld\n", ans%1000000007);
    return 0;
}

Palindromic Border C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define L 5000011
int sa[L];
int sai[L];
int lcp[L];
int v[L];
char s[L];
ll ts[L];
int p[L<<1];
char t[L<<1];
int m, n;
set<ll> found;
bool scomp(int i, int j) {
    return s[i] < s[j];
}
bool tscomp(int i, int j) {
    return ts[i] < ts[j];
}
void get_suffix_array() {
    for (int i = 0; i < n; i++) v[i] = i;
    sort(v, v + n, scomp);
    sai[v[0]] = 1;
    for (int i = 1; i < n; i++) {
        if (s[v[i]] == s[v[i - 1]]) {
            sai[v[i]] = sai[v[i - 1]];
        } else {
            sai[v[i]] = i+1;
        }
    }
    for (int p = 1; p <= n; p <<= 1) {
        for (int i = 0; i < n-p; i++) ts[i] = sai[i] * (n+1LL) + sai[i+p];
        for (int i = n-p; i < n; i++) ts[i] = sai[i] * (n+1LL);
        sort(v, v + n, tscomp);
        sai[v[0]] = 1;
        for (int i = 1; i < n; i++) {
            if (ts[v[i]] == ts[v[i - 1]]) {
                sai[v[i]] = sai[v[i - 1]];
            } else {
                sai[v[i]] = i+1;
            }
        }
    }
    for (int i = 0; i < n; i++) sai[i]--;
    for (int i = 0; i < n; i++) sa[sai[i]] = i;
}
void get_lcp() {
    for (int i = 0; i < n; i++) lcp[i] = 0;
    int l = 0;
    for (int i = 0; i < n-1; i++) {
        int k = sai[i];
        int j = k ? sa[k-1] : sa[n-1];
        while (j + l < n and s[i + l] == s[j + l]) {
            l++;
        }
        lcp[k] = l;
        if (l > 0) {
            l--;
        }
    }
}
void manacher() {
    // from wikipedia
    // t has been processed
    int center = 0, end = 0, left = 0, right = 0;
    for (int i = 1; i < m; i++) {
        if (i > end) {
            p[i] = 0;
            left = i - 1;
            right = i + 1;
        } else {
            int j = 2*center - i; // index on the other side
            if (p[j] < end - i) { // whole palindrome is inside
                p[i] = p[j];
                left = -1; // so we don't enter the loop below
            } else { 
                p[i] = end - i;
                right = end + 1;
                left = 2*i - right;
            }
        }
        while (left >= 0 and right < m and t[left] == t[right]) {
            p[i]++;
            left--;
            right++;
        }
        if (i + p[i] > end) {
            center = i;
            end = i + p[i];
        }
    }
}
struct Node {
    int i, j, v;
    Node *p, *l, *r;
    Node(int i, int j, Node *p = NULL): i(i), j(j), p(p) {
        if (j - i == 1) {
            l = r = NULL;
            v = lcp[i];
        } else {
            int k = i + j >> 1;
            l = new Node(i, k, this);
            r = new Node(k, j, this);
            v = min(l->v, r->v);
        }
    }
};
int node_minocc(Node *node, int v, int i) {
    // find maximum j, 0 <= j <= i such that a[j] < v
    while (node->l) {
        if (i < node->l->j) {
            node = node->l;
        } else {
            node = node->r;
        }
    }
    // now node->i = i < node->j = i+1
    if (node->v < v) {
        return node->i;
    }
    while (true) {
        while (node->p and node->p->l == node) {
            node = node->p;
        }
        if (!node->p) {
            return 0;
        }
        node = node->p;
        if (node->l->v < v) {
            node = node->l;
            break;
        }
    }
    while (node->l) {
        if (node->r->v < v) {
            node = node->r;
        } else {
            node = node->l;
        }
    }
    return node->i;
}
int node_maxocc(Node *node, int v, int i) {
    // find maximum j, i <= j <= n such that a[j] >= v
    if (i == n) {
        return n;
    }
    while (node->l) {
        if (i < node->l->j) {
            node = node->l;
        } else {
            node = node->r;
        }
    }
    // now node->i = i < node->j = i+1
    if (node->v < v) {
        return node->i;
    }
    while (true) {
        while (node->p and node->p->r == node) {
            node = node->p;
        }
        if (!node->p) {
            return n;
        }
        node = node->p;
        if (node->r->v < v) {
            node = node->r;
            break;
        }
    }
    while (node->l) {
        if (node->l->v < v) {
            node = node->l;
        } else {
            node = node->r;
        }
    }
    return node->i;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    // suffix tree
    get_suffix_array();
    get_lcp();
    Node *root = new Node(0, n);
    m = 0;
    for (int i = 0; i < n; i++) {
        t[m++] = '#';
        t[m++] = s[i];
    }
    t[m++] = '$';
    t[0] = '^';
    manacher();
    ll ans = 0;
    for (int i = 1; i < m-1; i++) {
        int k = p[i];
        if (t[i-k] == '#') k--;
        for(; k >= 0; k -= 2) {
            int start = sai[i-k>>1];
            int mino = node_minocc(root,k+1,start);
            ll hsh = k*(n+1LL)+mino;
            if (found.find(hsh) != found.end()) {
                break;
            }
            found.insert(hsh);
            int maxo = node_maxocc(root,k+1,start+1);
            ll c = maxo - mino;
            ans += c*(c-1);
            ans %= mod;
        }
    }
    ans = ans * (mod+1>>1) % mod;
    printf("%lld\n", ans);
}

Palindromic Border C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the palindromicBorder function below.
     */
    static int palindromicBorder(string s) {
        
        int m = 1000000007;

        GetPalindromeFrequencies(s, out TreeNode oddBaseNode, out TreeNode evenBaseNode);

        return (int)((oddBaseNode.SumFrequencyShit(m) + evenBaseNode.SumFrequencyShit(m)) % m);
    }

    public static int palindromicBorder2(string s)
    {
        if (s.Length <= 1)
            return 0;

        Manacher2(s, out var even, out var odd);
        odd.CascadeFrequenciesDown();
        even.CascadeFrequenciesDown();

        even.Frequency = 0;
        even.GetNext(0).Frequency = 0;
        odd.Frequency = 0;

        long m = 1000000007;


        long result = (odd.GetCount(2 * m, false, false) + even.GetCount(2 * m, false, true)) / 2 % m;
        return (int) result;
    }

    class TreeNode
    {
        public int Frequency;
        public TreeNode[] NextNodes;

        public long SumFrequencyShit(long m)
        {
            long result = (long)Frequency * ((long)Frequency - 1) / 2 % m;
            if (NextNodes == null)
                return result;
            for (int i = 0; i < NextNodes.Length; i++)
            {
                var node = NextNodes[i];
                if (node != null)
                {
                    result = (result + node.SumFrequencyShit(m)) % m;
                }
            }
            return result;
        }
    }

    static void GetPalindromeFrequencies(string s, out TreeNode oddBaseNode, out TreeNode evenBaseNode)
    {
        int[] letters = new int[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            letters[i] = (int)(s[i] - 'a');
        }

        oddBaseNode = new TreeNode();
        oddBaseNode.NextNodes = new TreeNode[8];
        evenBaseNode = new TreeNode();
        evenBaseNode.NextNodes = new TreeNode[8];
        for (int i = 0; i < letters.Length; i++)
        {
            var node = oddBaseNode.NextNodes[letters[i]];
            if (node == null)
            {
                node = new TreeNode();
                oddBaseNode.NextNodes[letters[i]] = node;
            }
            node.Frequency++;
            int max = Math.Min(i, letters.Length - i - 1);
            for (int j = 1; j <= max; j++)
            {
                int start = i - j;
                int end = i + j;
                if (letters[start] == letters[end])
                {
                    if (node.NextNodes == null)
                    {
                        node.NextNodes = new TreeNode[8];
                    }
                    var nextNode = node.NextNodes[letters[start]];
                    if (nextNode == null)
                    {
                        nextNode = new TreeNode();
                        node.NextNodes[letters[start]] = nextNode;
                    }
                    node = nextNode;
                    node.Frequency++;
                }
                else
                {
                    break;
                }
            }
            node = evenBaseNode.NextNodes[letters[i]];
            if (node == null)
            {
                node = new TreeNode();
                evenBaseNode.NextNodes[letters[i]] = node;
            }
            max = Math.Min(i + 1, letters.Length - i - 1);
            for (int j = 1; j <= max; j++)
            {
                int start = i - j + 1;
                int end = i + j;
                if (letters[start] == letters[end])
                {
                    if (node.NextNodes == null)
                    {
                        node.NextNodes = new TreeNode[8];
                    }
                    var nextNode = node.NextNodes[letters[start]];
                    if (nextNode == null)
                    {
                        nextNode = new TreeNode();
                        node.NextNodes[letters[start]] = nextNode;
                    }
                    node = nextNode;
                    node.Frequency++;
                }
                else
                {
                    break;
                }    
            }
        }
    }




    class TreeNode2
    {
        public long Frequency = 0;

        TreeNode2[] nextNodes = new TreeNode2[9];

        public TreeNode2 Parent;

        public TreeNode2 GetNext(int i)
        {
            var node = nextNodes[i];

            if (node == null)
            {
                node = new TreeNode2();
                node.Parent = this;
                nextNodes[i] = node;
            }

            return node;
        }

        public TreeNode2 GetParent(int depth)
        {
            if (depth == 0)
                return this;
            else
                return Parent.GetParent(depth - 1);
        }

        public long GetCount(long m, bool isEven, bool shouldSkip)
        {
            long result = 0;
            for (int i = 0; i < nextNodes.Length; i++)
            {
                var node = nextNodes[i];
                if (node != null)
                {
                    long count = node.GetCount(m, isEven, !shouldSkip);
                    result = (result + count) % m;
                }
            }

            if (isEven)
            {
                if (shouldSkip)
                {
                    return result;
                }
                else
                {
                    return (result + Frequency * (Frequency - 1) / 8) % m;
                }
            }
            else
            {
                return (result + Frequency * (Frequency - 1) / 2) % m;
            }

        }

        public void CascadeFrequenciesDown()
        {
            for (int i = 0; i < nextNodes.Length; i++)
            {
                var node = nextNodes[i];
                if (node != null)
                {
                    node.CascadeFrequenciesDown();
                    Frequency += node.Frequency;
                }
            }
        }

        public string Name;
        public void SetName(string s)
        {
            Name = s;
            for (int i = 0; i < nextNodes.Length; i++)
            {
                var node = nextNodes[i];
                if (node != null)
                {
                    if (s.Length == 0)
                        node.SetName(i.ToString());
                    else
                        node.SetName(i + s + i);
                }
            }
        }

        public override string ToString() => Name ?? "";
    }

    static int[] Manacher2(string s, out TreeNode2 evenBaseNode, out TreeNode2 oddBaseNode)
    {
        return Manacher2(ToInts(s), out evenBaseNode, out oddBaseNode);
    }

    static int[] Manacher2(int[] s, out TreeNode2 evenBaseNode, out TreeNode2 oddBaseNode)
    {
        int[] result = new int[s.Length];

        TreeNode2[] treeNodes = new TreeNode2[s.Length];

        oddBaseNode = new TreeNode2();
        evenBaseNode = new TreeNode2();

        int c = 0;
        int r = 0;
        int m = 0;
        int n = 0;

        treeNodes[0] = evenBaseNode.GetNext(s[0]);
        treeNodes[0].Frequency++;

        for (int i = 1; i < s.Length; i++)
        {
            treeNodes[i] = (i % 2 == 0 ? evenBaseNode : oddBaseNode).GetNext(s[i]);
            treeNodes[i].Frequency++;
            if (i > r)
            {
                result[i] = 0;
                m = i - 1;
                n = i + 1;
            }
            else
            {
                int j = 2 * c - i;
                if (result[j] <= r - i - 1)
                {
                    result[i] = result[j];
                    treeNodes[i].Frequency--;
                    treeNodes[i] = treeNodes[j];
                    treeNodes[i].Frequency++;
                    m = -1;
                }
                else
                {
                    result[i] = r - i;

                    treeNodes[i].Frequency--;
                    treeNodes[i] = treeNodes[j].GetParent(result[j] - result[i]);
                    treeNodes[i].Frequency++;


                    n = r + 1;
                    m = 2 * i - n;
                }
            }

            while (m >= 0 && n < s.Length && s[m] == s[n])
            {
                result[i]++;

                treeNodes[i].Frequency--;
                treeNodes[i] = treeNodes[i].GetNext(s[m]);
                treeNodes[i].Frequency++;
                m--;
                n++;
            }

            if (i + result[i] > r)
            {
                c = i;
                r = i + result[i];
            }
        }

        return result;
    }


    static int[] ToInts(string s)
    {
        int[] result = new int[s.Length * 2 + 1];

        for (int i = 0; i < s.Length; i++)
        {
            result[2 * i + 1] = (int) (s[i] - 'a' + 1);
        }
        return result;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string s = Console.ReadLine();

        int result = palindromicBorder2(s);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Palindromic Border Java Solution

import java.io.*;
import java.util.Arrays;

public class timus2040 {

    static int[][] es;
    static int[] slink, len, cnt;
    static int free;

    static int newNode(int l) {
        len[free] = l;
        return free++;
    }

    static int get(int i, char c) {
        return es[c - 'a'][i];
    }

    static void set(int i, char c, int n) {
        es[c - 'a'][i] = n;
    }

    public static void solve(Input in, PrintWriter out) throws IOException {
        char[] s = in.next().toCharArray();
        int n = s.length;
        es = new int[8][n + 2];
        for (int[] ar : es) {
            Arrays.fill(ar, -1);
        }
        len = new int[n + 2];
        slink = new int[n + 2];
        cnt = new int[n + 2];
        int root0 = newNode(0);
        int rootm1 = newNode(-1);
        slink[root0] = slink[rootm1] = rootm1;
        int cur = root0;
        for (int i = 0; i < n; ++i) {
            while (i - len[cur] == 0 || s[i] != s[i - len[cur] - 1]) {
                cur = slink[cur];
            }
            if (get(cur, s[i]) == -1) {
                set(cur, s[i], newNode(len[cur] + 2));
                if (cur == rootm1) {
                    slink[get(cur, s[i])] = root0;
                } else {
                    int cur1 = slink[cur];
                    while (s[i] != s[i - len[cur1] - 1]) {
                        cur1 = slink[cur1];
                    }
                    slink[get(cur, s[i])] = get(cur1, s[i]);
                }
            }
            cur = get(cur, s[i]);
            cnt[cur]++;
        }
        long ans = 0;
        for (int i = free - 1; i >= 0; --i) {
            cnt[slink[i]] += cnt[i];
            if (len[i] > 0) {
                ans = (ans + 1L * cnt[i] * (cnt[i] - 1) / 2) % 1000000007;
            }
        }
        out.println(ans);
    }

    public static void main(String[] args) throws IOException {
//        FileWriter out = new FileWriter("output.txt");
//        solve(new FileReader("input.txt"), out);
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}

Palindromic Border JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the palindromicBorder function below.
 */
function palindromicBorder(str) {
  const counter = {
    count: 0,
    devidedBy: 1e9 + 7,
    add (count) {
      this.count = this.count + count
      if (this.count >= this.devidedBy) this.count %= this.devidedBy
    }
  }
  const newBorderState = (border, j=0, k=1) => ({border: border, j: j, k: k, indices: []})
  const kinds = []
  const borderStateMap = {}
  'abcdefgh'.split('').forEach(char => {
    borderStateMap[char] = newBorderState(char)
    if (str.indexOf(char) !== -1) kinds.push(char)
  })
  
  if (kinds.length === 1) {
    const len = str.length
    counter.add(len * (len + 1) * (len - 1) / 6)
    return counter.count
  }
  
  for (let i=0; i < str.length; i++) {
    borderStateMap[str[i]].indices.push(i)
  }
  
  
  
  
  
  const borderStateArray = []
  for (const char of Object.keys(borderStateMap)) {
    let j = borderStateMap[char].j
    let alive = borderStateMap[char].indices
    delete borderStateMap[char]
    while (alive.length) {
      const i = alive[0]
      while (i === alive[0]) {
        const prevBorder = str.slice(i, i+j)
        const borderState = newBorderState(prevBorder, j-1)
        alive = alive.filter(l => {
          if (str[l+j] === char) return true
          else if (str[l+j]) return void borderState.indices.push(l)
          else return false
        })
        counter.add(alive.length * (alive.length - 1) / 2)
        if (borderState.indices.length) borderStateArray.push(borderState)
        j++
      }
    }
  }
  
  
  while (borderStateArray.length) {
    const index = borderStateArray.length-1
    const j = borderStateArray[index].j
    let k = borderStateArray[index].k
    let alive = borderStateArray[index].indices
    borderStateArray.pop()
    while (alive.length) {
      const i = alive[0]
      while (i === alive[0]) {
        const char = str[i+j+k]
        const prevBorder = str.slice(i-k+1, i+j+k-1)
        const borderState = newBorderState(prevBorder, j, k)
        alive = alive.filter(l => {
          const curr0 = str[l-k]
          const curr1 = str[l+j+k]
          if (!curr1) return false
          else if (curr0 === char && curr1 === char) return true
          else if (curr0 === curr1) return void borderState.indices.push(l)
          else return false
        })
        counter.add(alive.length * (alive.length - 1) / 2)
        if (borderState.indices.length) borderStateArray.push(borderState)
        k++
      }
    }
  }
  return counter.count
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const s = readLine();

    let result = palindromicBorder(s);

    ws.write(result + "\n");

    ws.end();
}

Palindromic Border Python Solution

def mod(x):
    return x % 1000000007

class trie(object):
    def __init__(self, depth=0, parent=None, data=None):
        self.count = 0
        self.depth = depth
        self.parent = parent
        self.data = data
        self.next = {}
        
    def get(self, char):
        if char in self.next:
            return self.next[char]
        ans = trie(self.depth + 2, self, char)
        self.next[char] = ans
        return ans
    
    def children(self):
        return self.next.values()

def dfs(node):
    ans = 0
    stack = []
    stack.append((node, True))
    while len(stack) > 0:
        node, extend = stack.pop()
        if extend:
            stack.append((node, False))
            for child in node.children():
                stack.append((child, True))
        else:
            for child in node.children():
                node.count += child.count
            if node.depth > 0:
                ans = mod(ans + mod(node.count * (node.count - 1) // 2))
    return ans

def pr(node):
    print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
    for child in node.children():
        pr(child)

def score(string):
    # ascii values
    string = list(map(ord, string))
    N = len(string)*2 + 1
    c = [0] * N
    c[1::2] = string
    # initialize trie pointers
    odd = trie(depth = -1)
    even = trie()
    center, radius = 0, 0
    left, right = 0, 0
    # manacher's algorithm
    node = [even]
    span = [0]
    for i in range(1, N):
        if i > radius:
            node.append(odd.get(c[i]) if (i & 1) else even)
            span.append(0)
            left = i - 1
            right = i + 1
        else:
            mirror = center * 2 - i
            if span[mirror] < radius - i:
                span.append(span[mirror])
                node.append(node[mirror])
                left = -1
            else:
                span.append(radius - i)
                node.append(node[mirror])
                while node[i].depth > radius - i:
                    node[i] = node[i].parent
                right = radius + 1
                left = i * 2 - right
        while left >= 0 and right < N and c[left] == c[right]:
            if c[right]:
                node[i] = node[i].get(c[right])
            span[i] += 1
            left -= 1
            right += 1
        node[i].count += 1
        if i + span[i] > radius:
            center = i
            radius = i + span[i]
    # accumulate count
    return mod(dfs(odd) + dfs(even))
    
print(score(str(input())))
c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post

Leave a Reply

You must be logged in to post a comment.

  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes