Palindromic Border

                            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[] slink, len, cnt;
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);
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);
}



}










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