BOJ. Longest Palindrome Substring (13275)

Problem: BOJ 13275 — Longest Palindrome Substring · 한국어 · 日本語

Manacher’s algorithm stores the palindrome radius at every possible center. Odd-length palindromes are centered on a character: radiusOdd[i] counts the center itself, so its palindrome has length 2 * radiusOdd[i] - 1. Even-length palindromes are centered in the gap immediately before i: radiusEven[i] is the number of matching pairs around that gap, giving length 2 * radiusEven[i].

For each kind of center, keep [left, right], the rightmost palindrome found so far. If the next center i is inside that interval, reflect it across the interval’s center to find its mirror. The mirror’s known radius can be reused, but only up to right - i + 1, the portion guaranteed to remain inside the known palindrome. If i lies outside the interval, start with the smallest possible radius (one character for odd centers, zero pairs for even centers). Then compare characters immediately outside the current radius and expand while they match. Whenever the expanded palindrome extends farther right, update [left, right].

Every successful expansion moves the right boundary forward, so the total work is linear. The answer is the larger of all odd and even palindrome lengths. The algorithm takes O(N) time and O(N) space, which handles strings of length up to 10^6.

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s;
  cin >> s;
  const int n = static_cast<int>(s.size());

  vector<int> radiusOdd(n);
  vector<int> radiusEven(n);
  int longest = 1;

  int left = 0;
  int right = -1;
  for (int i = 0; i < n; ++i) {
    int radius = (i > right)
                     ? 1
                     : min(radiusOdd[left + right - i], right - i + 1);
    while (i - radius >= 0 && i + radius < n &&
           s[i - radius] == s[i + radius]) {
      ++radius;
    }
    radiusOdd[i] = radius;
    longest = max(longest, 2 * radius - 1);

    if (i + radius - 1 > right) {
      left = i - radius + 1;
      right = i + radius - 1;
    }
  }

  left = 0;
  right = -1;
  for (int i = 0; i < n; ++i) {
    int radius = (i > right)
                     ? 0
                     : min(radiusEven[left + right - i + 1], right - i + 1);
    while (i - radius - 1 >= 0 && i + radius < n &&
           s[i - radius - 1] == s[i + radius]) {
      ++radius;
    }
    radiusEven[i] = radius;
    longest = max(longest, 2 * radius);

    if (i + radius - 1 > right) {
      left = i - radius;
      right = i + radius - 1;
    }
  }

  cout << longest << '\n';
}