Поиск всех палиндромов

#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int N = 2e5 + 3;
const ull base = 29;

ull h[2][N], b[N];
string s;
int n;

ull get(int i, int j, int k) {
    if (k == 0) {
        if (i == 0) {
            return h[k][j];
        }
        return (h[k][j] - h[k][i - 1] * b[j - i + 1]);
    } else {
        if (j + 1 == n) {
            return h[k][i];
        }
        return (h[k][i] - h[k][j + 1] * b[j - i + 1]);
    }
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);
    cin >> s;
    n = s.size();
    b[0] = 1;
    for (int i = 1; i <= n; ++i) {
        b[i] = b[i - 1] * base;
    }

    h[0][0] = s[0];
    for (int i = 1; i < n; ++i) {
        h[0][i] = (h[0][i - 1] * base + s[i]);
    }

    h[1][n - 1] = s[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        h[1][i] = (h[1][i + 1] * base + s[i]);
    }

    long long res = 0;

    for (int i = 0; i < n; ++i) {
        int low = 1, high = min(i, n - 1 - i), ans = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (get(i - mid, i, 0) == get(i, i + mid, 1)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        res += ans + 1;

        if (!(i + 1 < n && s[i] == s[i + 1])) {
            continue;
        }

        low = 1, high = min(i, n - 2 - i), ans = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (get(i - mid, i, 0) == get(i + 1, i + 1 + mid, 1)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        res += ans + 1;
    }

    cout << res;

    return 0;
}