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
3Explanation
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
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())))
