pallindromic tree

/* pallindromic tree */

//when indx based calcu is required

ll tree[MAX][30],idx,link[MAX],len[MAX],t,pree[MAX][30],cnt;char s[MAX];ll occ[MAX];ll ans1[MAX],ans2[MAX];ll f[MAX],e[MAX];

void initialize()
{
    len[1] = -1;
    len[2] = 0;
    link[1] = 1;
    link[2] = 1;
    t = idx = 2;
    mem(tree,0);
    mem(occ,0);
}

int extend(int p){
    int save;
    while(s[p - len[t] - 1] != s[p]) t = link[t];
    int x = link[t], c = s[p] - 'a';
    while(s[p - len[x] - 1] != s[p]) x = link[x];
    if(!tree[t][c]) {
        tree[t][c] = ++idx;
        save = idx;
        len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][c];
    }
    else {
        save = tree[t][c];
    }
     t = tree[t][c];
     return save;
}



int main()
{
    //booster()
    ///read("input.txt");


        scanf(" %s",s+1);

        initialize();int l = strlen(s+1);
        for(int i = 1;i<=l;i++){
            int x = extend(i);
            f[i] = x;
        }

        for(int i = 3;i<=idx;i++){
            occ[i]+=occ[link[i]] + 1;
        }
        for(int i = 1;i<=l;i++){
            int x = f[i];
            ans1[i] = occ[x];
        }
        string s2 = s+1;
        reverse(all(s2));

        for(int i = 1;i<=l;i++)s[i] = s2[i-1];
        initialize();
        for(int i = 1;i<=l;i++){
            int x = extend(i);
            e[i] = x;
        }
        for(int i = 3;i<=idx;i++){
            occ[i]+=occ[link[i]] + 1;
        }
        for(int i = 1;i<=l;i++){
            ans2[l-i+1] = occ[e[i]];
        }

        //for(int i = 1;i<=l;i++)cout<<ans1[i]<<" "<<ans2[i]<<endl;

        for(int i = l-1;i>=1;i--)ans2[i]+=ans2[i+1];

        ull ans = 0;
        for(int i = 1;i<=l-1;i++){
            //if(ans1[i]&&ans2[i+1])
            ans+=(ans1[i] * ans2[i+1]);
        }
        cout<<ans<<endl;



    return 0;
}



// when pallindromic substring based calcu is required

int tree[MAX][30],idx,link[MAX],len[MAX],t,pree[MAX][30],cnt;char s[MAX];ll occ[MAX];

void initialize()
{
    len[1] = -1;
    len[2] = 0;
    link[1] = 1;
    link[2] = 1;
    t = idx = 2;
}

void extend(int p){
    while(s[p - len[t] - 1] != s[p]) t = link[t];
    int x = link[t], c = s[p] - 'a';
    while(s[p - len[x] - 1] != s[p]) x = link[x];
    if(!tree[t][c]) {
        tree[t][c] = ++idx;
        occ[idx]++;
        len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][c];
    }
    else occ[tree[t][c]]++;
     t = tree[t][c];
}

int main()
{
    //booster()
    ///read("input.txt");


        scanf(" %s",s+1);

        initialize();int l = strlen(s+1);
        for(int i = 1;i<=l;i++){
            extend(i);
        }

        for(int i = idx;i>2;i--){
            occ[link[i]]+=occ[i];
        }
        ll ans = 0;
        for(int i = idx;i>2;i--)ans+=occ[i];
        cout<<ans;



    return 0;
}