OhZEHV - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>

using namespace std;

#define mset(x,val) memset(x,val,sizeof(x))
#define allof(x) x.begin(), x.end()
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vb = vector<bool>;
using vbb = vector<vector<bool>>;
using mii = map<int,int>;
using umii = unordered_map<int,int>;
using pii = pair<int,int>;
using pll = pair<long long,long long>;
using pli = pair<long long, int>;
using pil = pair<int, long long>;
#define __builtin_popcount __builtin_popcountll
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))
#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;

int a, b, m, n, k, q;

struct Eertree
{
    struct Node
    {
        int len;
        int link;
        int next[26];
        int cnt;
        int s_cnt;
        int first_pos;

        Node (int _n)
        {
            len = _n;
            link = 0;
            cnt = 0;
            s_cnt = 0;
            mset(next, 0);
        }
    };

    int n;
    vector <Node> tree;
    string s;
    int last;

    Eertree(int _n)
    {
        n = _n;
        tree.reserve(n+3);
        tree.push_back(Node(-1));
        tree.push_back(Node(0));

        tree[0].link = 0;
        tree[1].link = 0;

        last = 1;
        s="";
    }

    int get_link(int v, int pos)
    {
        while (1)
        {
            int curlen = tree[v].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
            v = tree[v].link;
        }
        return v;
    }

    void add_char(char c)
    {
        int pos = s.size();
        s+=c;
        int cur = get_link(last, pos);

        int cidx = c-'a';

        if (tree[cur].next[cidx])
        {
            last = tree[cur].next[cidx];
            tree[last].cnt++;
            tree[last].s_cnt++;
            return;
        }

        int new_node = tree.size();
        tree.push_back(Node(tree[cur].len + 2));
        tree[new_node].first_pos = pos;

        tree[cur].next[cidx] = new_node;

        if (tree[new_node].len == 1) tree[new_node].link = 1;
        else
        {
            int num = get_link(tree[cur].link, pos);
            tree[new_node].link = tree[num].next[cidx];
        }

        tree[new_node].cnt = 1;
        tree[new_node].s_cnt = 1;
        last = new_node;
    }

    void build(string str)
    {
        for (char c : str) add_char(c);
    }

    void propagate()
    {
        for (int i=tree.size()-1; i>=2; --i)
        {
            tree[tree[i].link].s_cnt += tree[i].s_cnt;
        }
    }

    int distinct_palin_cnt()
    {
        return tree.size() - 2;
    }

    int palin_cnt()
    {
        int res=0;

        for (int i=2; i<tree.size(); ++i) res+=tree[i].s_cnt;

        return res;
    }


};

string s;

void Input()
{
    cin>>s;
    Eertree Eet = Eertree(s.size());
    Eet.build(s);
    Eet.propagate();
    cout<<Eet.palin_cnt();

}

int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Input();
    return 0;
}