Counting Subpalindromes

#include <bits/stdc++.h>

using namespace std;

#define For(i, n)           for(int i = 0; i < n; ++i)
#define all(x)              (x).begin(),(x).end()
#define rall(x)             (x).rbegin(),(x).rend()

#define ld                  long double
#define pii                 pair<int, int>
#define vt                  vector
#define ll                  long long
#define endl                '\n'

const int MAX = 1e9;
const int MOD = 1e9 + 7;
const ll  INF = 1e18;
const ld  PI  = 3.14159265358979323846;

template<typename T>
void read(vt<T> & a) {
    For(i, a.size()) cin >> a[i];
}
template<typename T>
void print(vt<T> & a) {
    For(i, a.size()) cout << a[i] << " ";
    cout << endl;
}
template<typename T>
void print2(vt<vt<T> > & a) {
    For(i, a.size()) {
        For(j, a[i].size()) cout << a[i][j] << " ";
        cout << endl;
    }
}
template<typename T>
void read2(vt<vt<T> > & a) {
    For(i, a.size()) For(j, a[i].size()) cin >> a[i][j];
}

void solve()
{
    string s; cin >> s;
    int n = s.size();
    vt<ll> hash(n + 1);
    vt<ll> power(n + 1, 1);
    For(i, n) {
        hash[i + 1] = hash[i] + power[i] * (s[i] - 'a' + 1);
        power[i + 1] = power[i] * 31;
    }
    vt<ll> rhash(n + 1);
    reverse(all(s));
    For(i, n) {
        rhash[i + 1] = rhash[i] + power[i] * (s[i] - 'a' + 1);
    }

    ll ans = 0;
    For(i, n) {
        int l = 0, r = min(n - i - 1, i), m;
        while (l < r) {
            m = (l + r + 1) >> 1;
            int lb1 = i - m;
            int rb1 = i;
            int lb2 = n - (i + m) - 1;
            int rb2 = n - i - 1;

            int offset1 = lb1;
            int offset2 = lb2;
            ll h1 = hash[rb1 + 1] - hash[lb1];
            ll h2 = rhash[rb2 + 1] - rhash[lb2];
            if (offset1 > offset2) {
                h2 *= power[offset1 - offset2];
            } else {
                h1 *= power[offset2 - offset1];
            }
            if (h1 == h2) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        ans += l + 1;
    }
    For(i, n) {
        int l = -1, r = min(n - i - 2, i), m;
        while (l < r) {
            m = (l + r + 1) >> 1;
            int lb1 = i - m;
            int rb1 = i;
            int lb2 = n - (i + m) - 1 - 1;
            int rb2 = n - i - 1 - 1;

            int offset1 = lb1;
            int offset2 = lb2;
            ll h1 = hash[rb1 + 1] - hash[lb1];
            ll h2 = rhash[rb2 + 1] - rhash[lb2];
            if (offset1 > offset2) {
                h2 *= power[offset1 - offset2];
            } else {
                h1 *= power[offset2 - offset1];
            }

            if (h1 == h2) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        ans += l + 1;
    }
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #define FILE
#ifdef FILE
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    cout << setprecision(20) << fixed;
    int T = 1;
    For(t, T) {
        solve();
    }
    return 0;
}