Longest palindrome

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
 
const int A = 911382323;
const int B = 972663749;
const int N = 1e6;
int P[N];
 
vi hh(const string& a) {
  vi h(sz(a));
  h[0] = a[0];
  rep(i,1,sz(a)) {
    h[i] = (h[i-1]*ll(A) + a[i]) % B;
  }
  return h;
}
 
int hget(const vi& h, int a, int b) {
  if (a == 0) return h[b];
  int r = (h[b] - h[a-1]*ll(P[b-a+1])) % B;
  return r < 0 ? r + B : r;
}
 
int hcomp(const vi& a, const vi& b, const string& as, const string& bs) {
  int i = -1;
  int n = min(sz(a),sz(b));
  for (int s = 1<<20; s >= 1; s /= 2) {
    i += s;
    if (i >= n || a[i] != b[i]) i -= s;
  }
  return i == n ? sz(a) - sz(b) : as[i+1] - bs[i+1];
}
 
bool isPalidrom(const vi& s, const vi& rs, int a, int b) {
  return hget(s,a,b) == hget(rs,sz(rs)-1-b,sz(rs)-1-a);
}
 
int main() {
  P[0] = 1;
  rep(i,1,N) P[i] = ll(A) * P[i-1] % B;
  string a;
  cin >> a;
  int n = sz(a);
  vi h = hh(a);
  reverse(all(a));
  vi rh = hh(a);
  int ans = 0, anss = 0;
  rep(i,0,n) {
    int j = 0;
    for (int s = 1<<20; s >= 1; s /= 2) {
      j += s;
      if (i+j >= n || i-j < 0 || !isPalidrom(h,rh,i-j,i+j)) j -= s;
    }
    if (j*2+1 > anss) {
      ans = i-j;
      anss = j*2+1;
    }
    j = -1;
    for (int s = 1<<20; s >= 1; s /= 2) {
      j += s;
      if (i+j+1 >= n || i-j < 0 || !isPalidrom(h,rh,i-j,i+j+1)) j -= s;
    }
    if (j*2+2 > anss) {
      ans = i-j;
      anss = j*2+2;
    }
  }
  reverse(all(a));
  cout << string_view(a).substr(ans,anss);
}

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