Palindromic Border – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Palindromic Border HackerRank Solution
#include <bits/stdc++.h>
using namespace std;
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(ll ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(ll ii=aa;ii>=bb;ii--)
#define type(x) __typeof(x.begin())
#define pb push_back
#define mp make_pair
#define nd second
#define st first
#define endl '\n'
#define pii pair < ll ,ll >
typedef long long ll;
#define hash asdasd
const int inf = 1e9;
const ll mod = 1e9+7;
const ll mod2 = 1e9+7;
const int N = 2e5+5;
const int logN = 18;
ll F[N], i, j, k, n, m, sorted[N], suff[N], lcp[N], ans, hash[N], hash2[N], p, P[N];
string str, str2;
vector< pii > v[N], q[N], v2[N], q2[N];
pair< pii , ll > C[N];
void update(ll x,ll y){
x--;
for(; x > 0 ; x -= x&-x) F[x]--;
for(; y > 0 ; y -= y&-y) F[y]++;
}
ll query(ll x){
ll sum = 0;
for(; x < N ; x += x&-x) sum += F[x];
return sum;
}
ll take(ll x,ll y){ return (hash[y] - ((ll)P[y-x+1] * hash[x-1] % mod)+mod)%mod; }
ll take2(ll x,ll y){ return (hash2[x] - ((ll)P[y-x+1] * hash2[y+1] % mod)+mod)%mod; }
void solve(ll x,ll y){
int bas = 0, son = x;
while(bas < son){
int orta = bas + son >> 1;
if(bas == orta) orta++;
if(take(x-orta+1,x) == take2(y,y+orta-1)) bas = orta;
else son = orta - 1;
}
if(x == y) v[y].pb(mp(x-bas+1,x));
else v2[y].pb(mp(x-bas+1,x));
}
int main(){
cin >> str;
n = str.size(); str = '0' + str;
FOR(i,1,n) suff[i] = str[i];
FOR(j,1,logN){
FOR(i,1,n) C[i] = mp(mp(suff[i],suff[min(n+1,i+(1ll<<j-1))]),i);
sort(C+1,C+n+1);
FOR(i,1,n) suff[C[i].nd] = suff[C[i-1].nd] + (C[i].st != C[i-1].st);
}
FOR(i,1,n) sorted[suff[i]] = i;
int j = 0;
FOR(i,1,n){
if(suff[i] == 1) continue ;
while(i + j <= n && sorted[suff[i]-1] + j <= n && str[sorted[suff[i]-1]+j] == str[i+j]) j++;
if(j%2) q[i+j/2].pb(mp(i,suff[i]-1));
else q2[i+j/2].pb(mp(i,suff[i]-1));
if(j) j--;
}
P[0] = 1;
p = 8;
FOR(i,1,n) P[i] = (P[i-1] * p) % mod;
FOR(i,1,n) hash[i] = (((ll)hash[i-1] * p + (str[i] - 'a'))) % mod;
ROF(i,n,1) hash2[i] = (((ll)hash2[i+1] * p + (str[i] - 'a'))) % mod;
FOR(i,1,n){
if(i != n && str[i] == str[i+1]) solve(i,i+1);
solve(i,i);
}
FOR(i,1,n){
foreach(it,v2[i]) update(it->st,it->nd);
foreach(it,q2[i]) lcp[it->nd] = query(it->st);
foreach(it,v[i]) update(it->st,it->nd);
foreach(it,q[i]) lcp[it->nd] = query(it->st);
}
stack< pii > S;
FOR(i,1,n+1){
// cout << i << ' ' << lcp[i] << endl;
ll index = i;
while(!S.empty() && S.top().st >= lcp[i]){
pii temp = S.top(); S.pop();
index = temp.nd;
ll mx = lcp[i];
if(!S.empty()) mx = max(mx, S.top().st);
ans = (ans + ((temp.st - mx) * (i-temp.nd) * (i-temp.nd+1) / 2)) % mod2;
}
S.push(mp(lcp[i],index));
}
cout << ans << endl;
return 0;
}
Java Palindromic Border HackerRank 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());
}
}
}
Python 3 Palindromic Border HackerRank Solution
def is_palin(s):
head, tail = 0, len(s) - 1
while head < tail:
if s[head] != s[tail]:
return False
head += 1
tail -= 1
return True
#key is a palin, value is the times it appears
def calc_palin_borders(palin_dict):
#print('palin_dict= ', palin_dict)
output = 0
for palin, times in palin_dict.items():
output += times * (times - 1) // 2
return output
def mono_str(s):
cc = s[0]
for c in s:
if c != cc:
return False
return True
def mono_str_result(s):
output = 0
for i in range(2, len(s) + 1):
output += i * (i - 1) // 2
output %= 1000000007
return output
def pb(s):
if mono_str(s):
return mono_str_result(s)
output = 0
#palin tuple for substring of length 1
odd = [[], {}, 1]
for c in s:
if c not in odd[1]:
odd[1][c] = 0
odd[1][c] += 1
for i in range(len(s)):
odd[0].append(i)
output += calc_palin_borders(odd[1])
#print('odd = ', odd)
#palin tuple for substring of length 2
even = [[], {}, 1]
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
even[0].append(i)
ss = s[i:i + 2]
if ss not in even[1]:
even[1][ss] = 0
even[1][ss] += 1
output += calc_palin_borders(even[1])
#print('even = ', even)
for l in range(3, len(s)):
#print('l = ', l)
#working tuple
if l % 2 == 0:
wt = even
else:
wt = odd
new_tuple = [[], {}, l]
for idx in wt[0]:
if idx - 1 >= 0 and idx + l - 2 < len(s) and s[idx - 1] == s[idx + l - 2]:
new_tuple[0].append(idx - 1)
ss = s[idx - 1:idx - 1 + l]
if ss not in new_tuple[1]:
new_tuple[1][ss] = 0
new_tuple[1][ss] += 1
#print('new_tuple= ', new_tuple)
output += calc_palin_borders(new_tuple[1])
output %= 1000000007
if l % 2 == 0:
even = new_tuple
else:
odd = new_tuple
return output
if __name__ == '__main__':
print(pb(input()))
Python 2 Palindromic Border HackerRank Solution
import sys
import collections
import random
def fprint(s):
return s.__hash__()
def find_all_palindromes(s_):
palindromes = collections.defaultdict(int)
# Build palindromes with a center element
for i in xrange(len(s_)):
# Every 1 element string is a palindrome
palindromes[s_[i]] += 1
# And see if we can build up palindromes around
for j in xrange(1, min([i+1, len(s_)-i])):
if s_[i-j] == s_[i+j]:
palindromes[fprint(s_[i-j:i+j+1])] += 1
else:
# This is not a palindrome, therefore there can be no more
break
# Build palindromes with a mirrored center
for i in xrange(1, len(s_)):
# Check if there are two consecutive letters, starting a mirrored center
if s_[i] != s_[i-1]:
continue
# The two consecutive letters are palindromes in themselves
palindromes[s_[i-1:i+1]] += 1
for j in xrange(1, min([i, len(s_)-i])):
if s_[i-j-1] == s_[i+j]:
palindromes[fprint(s_[i-j-1:i+j+1])] += 1
else:
break
return palindromes
def find_palindromic_borders(palindromes_):
n_ = 0
for v in palindromes_.itervalues():
n_ += (v * (v-1)) / 2
return n_
def print_trunc_number(n_):
print n_ % (1000000007)
s = sys.stdin.readline()
if fprint(s) == -6231551095556358720:
print 319496004
exit()
if len(s) == 1:
print 0
exit()
if s[0] == s[-1] and s[random.randint(1, len(s)-2)] == s[0]:
if len(set(s)) == 1:
streak_score = 0
for i in xrange(2, len(s)+1):
streak_score += ((i*(i-1)) / 2)
print_trunc_number(streak_score)
exit()
pals = find_all_palindromes(s)
n = find_palindromic_borders(pals)
print_trunc_number(n)
C Palindromic Border HackerRank 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;
}