# Palindromic Border

### Problem Statement :

```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  as the number of palindromic borders of string . For example, if  lololol, then .

Now, a string of length  has exactly  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 , consisting only of the first 8 lowercase letters of the English alphabet, your task is to find the sum of  for all the non-empty substrings  of . In other words, you need to find:

where  is the substring of  starting at position  and ending at position .
Since the answer can be very large, output the answer modulo .

Input Format

The first line contains a string consisting of  characters.

Output Format

Print a single integer: the remainder of the division of the resulting number by 10^9 + 7.

Constraints

1  <=  N  <=  10^5

All characters in the string can be any of the first 8 lowercase letters of the English alphabet (abcdefgh).```

### Solution :

```                            ```Solution in C :

In  C++  :

#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;
}

In   Java  :

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

public class Solution {

static int[][] es;
static int free;

public static void main(String[] args)
throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Scanner(System.in), out);
out.close();
}
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(Scanner 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);
int cur = root0;
for (int i = 0; i < n; ++i) {
while (i - len[cur] == 0 || s[i] != s[i - len[cur] - 1]) {
}
if (get(cur, s[i]) == -1) {
set(cur, s[i], newNode(len[cur] + 2));
if (cur == rootm1) {
} else {
while (s[i] != s[i - len[cur1] - 1]) {
}
}
}
cur = get(cur, s[i]);
cnt[cur]++;
}
long ans = 0;
for (int i = free - 1; i >= 0; --i) {
if (len[i] > 0) {
ans = (ans + 1L * cnt[i] * (cnt[i] - 1) / 2) % 1000000007;
}
}
out.println(ans);
}

}

In    C  :

#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;
}

In   Python3 :

def is_palin(s):
head, tail = 0, len(s) - 1
return False
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()))```
```

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio