NC236738.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 300010;
using i64 = long long;
#define pb push_back
int tot, idx, last;
int fail[N], tr[N][26], len[N], cnt[N], w[N];
char s[N];
vector<int> G[N];

int create(int l) {
    idx++;
    memset(tr[idx], 0, sizeof tr[idx]);
    len[idx] = l;
    fail[idx] = 0;
    return idx;
}

void init() {
    idx = -1;
    tot = 0;
    s[0] = '$';
    last = 0;
    create(0);
    create(-1);
    fail[0] = 1;
}

int getfail(int x) {
    while (s[tot - 1 - len[x]] != s[tot]) x = fail[x];
    return x;
}

int insert(char ch) {
    s[++tot] = ch;
    int now = getfail(last);
    int p = ch - 'a';
    if (!tr[now][p]) {
        int x = create(len[now] + 2);
        fail[x] = tr[getfail(fail[now])][p];
        tr[now][p] = x;
        w[x] = w[now] | (1 << p);
    }
    cnt[last = tr[now][p]]++;
    return last;
}

void dfs(int u) {
    for (int to: G[u]) {
        dfs(to);
        cnt[u] += cnt[to];
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    init();
    for (char ch: s) insert(ch);
    for (int i = 2; i <= idx; i++) G[fail[i]].pb(i);
    dfs(0);
    i64 ans = 0;
    for (int i = 2; i <= idx; i++) ans += __builtin_popcount(w[i]) * cnt[i];
    cout << ans << '\n';
    return 0;
}