Longest palindrome

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e6 + 5;
const int P = 29;
const int MOD = 1e9 + 7;

void add(int &a, int b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}

void sub(int &a, int b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
}

int mul(int a, int b) {
  return 1LL * a * b % MOD;
}

int n;
string a, b;
int pp[N];
int hh[N], kk[N];

int get_a(int l, int r) {
  if (l == 0) {
    return hh[r];
  }
  int res = hh[r];
  sub(res, mul(hh[l - 1], pp[r - l + 1]));
  return res;
}

int get_b(int l, int r) {
  if (l == 0) {
    return kk[r];
  }
  int res = kk[r];
  sub(res, mul(kk[l - 1], pp[r - l + 1]));
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  pp[0] = 1;
  for (int i = 1; i < N; i++) {
    pp[i] = mul(P, pp[i - 1]);
  }
  cin >> a;
  b = a;
  reverse(b.begin(), b.end());
  n = b.size();
  for (int i = 0; i < n; i++) {
    hh[i] = (i > 0 ? hh[i - 1] : 0);
    hh[i] = mul(hh[i], P);
    add(hh[i], a[i] - 'a' + 1);

    kk[i] = (i > 0 ? kk[i - 1] : 0);
    kk[i] = mul(kk[i], P);
    add(kk[i], b[i] - 'a' + 1);
  }
  int ll = -1, rr = -2;
  for (int i = 0; i < n; i++) {
    int lo = 1, hi = min(i + 1, n - i), ans = -1;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (get_a(i - mid + 1, i) == get_b(n - 1 - (i + mid - 1), n - 1 - i)) {
        ans = mid;
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    if (ans * 2 - 1 > rr - ll + 1 && ans != -1) {
      ll = i - ans + 1;
      rr = i + ans - 1;
    }
  }
  for (int i = 0; i < n - 1; i++) {
    if (a[i] == a[i + 1]) {
      int lo = 1, hi = min(i + 1, n - i - 1), ans = -1;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (get_a(i - mid + 1, i) == get_b(n - 1 - (i + mid), n - 1 - i - 1)) {
          ans = mid;
          lo = mid + 1;
        } else {
          hi = mid - 1;
        }
      }
      if (ans * 2 > rr - ll + 1 && ans != -1) {
        ll = i - ans + 1;
        rr = i + 1 + ans - 1;
      }
    }
  }
  cout << a.substr(ll, rr - ll + 1) << '\n';
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED