llindromic tree
const int MAXN = 105000;
struct node
{
    int next[26];
    int len;
    int sufflink;
    int num;
};
int len;
char s[MAXN];
node tree[MAXN];
int num; // node 1 - root with len -1, node 2 - root with len 0
int suff; // max suffix palindrome
long long ans;
bool addLetter(int pos)
{
    for( int i = 0 ; i < 50 ; i++ ) cout << "- " ;
    cout << endl ;
    int cur = suff, curlen = 0;
    int let = s[pos] - 'a';
    cout << "after curr = suff : cur = "<< cur << endl ;
    cout << "let = " << let << endl ;
    while (true)
    {
        curlen = tree[cur].len;
        cout << "in first while loop : cur = " << cur << " & curlen " << curlen << " & pos = " << pos << endl ;
        if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
            break;
        cur = tree[cur].sufflink;
    }
    if (tree[cur].next[let])
    {
        cout << "here if(tree[cur].next[let]) = " << tree[cur].next[let] << endl ;
        suff = tree[cur].next[let];
        return false;
    }
    num++;
    suff = num;
    tree[num].len = tree[cur].len + 2;
    tree[cur].next[let] = num;
    cout << " num++ then, num = " << num << endl ;
    if (tree[num].len == 1)
    {
        tree[num].sufflink = 2;
        tree[num].num = 1;
        return true;
    }
    while (true)
    {
        cur = tree[cur].sufflink;
        curlen = tree[cur].len;
        cout << "in 2nd while loop : cur = " << cur << " & curlen " << curlen << " & pos = " << pos << endl ;
        if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
        {
            tree[num].sufflink = tree[cur].next[let];
            break;
        }
    }
    tree[num].num = 1 + tree[tree[num].sufflink].num;
    return true;
}
void initTree()
{
    num = 2;
    suff = 2;
    tree[1].len = -1;
    tree[1].sufflink = 1;
    tree[2].len = 0;
    tree[2].sufflink = 1;
}
int main()
{
    gets(s);
    len = strlen(s);
    initTree();
    for (int i = 0; i < len; i++)
    {
        addLetter(i);
        ans += tree[suff].num;
        cout << "\n\n" << ans << "\n\n" ;
    }
    cout << endl ;
    for( int i = 0 ; i < 50 ; i++ ) cout << " -" ;
    cout << endl;
    cout << ans << endl;
}