LPS_using_Manacher_algorithm.cpp

int Manacher(string s) {
  int n = sz(s);

  vector<int> d1(n);
  for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
    while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
      k++;
    }
    d1[i] = k--;
    if (i + k > r) {
      l = i - k;
      r = i + k;
    }
  }

  vector<int> d2(n);
  for (int i = 0, l = 0, r = -1; i < n; i++) {
    int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
      k++;
    }
    d2[i] = k--;
    if (i + k > r) {
      l = i - k - 1;
      r = i + k;
    }
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans = max(ans, 2 * d1[i] - 1); // d1[i] is no. of odd length palindromic
                                   // substrings centered at i
    ans = max(ans, 2 * d2[i]); // d2[i] is no. of even length palidromic
                               // substrings centered(left) at i
  }
  return ans;
}