結果

問題 No.273 回文分解
コンテスト
ユーザー C
提出日時 2026-10-08 00:35:31
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1 ms / 2,000 ms
+ 421µs
コード長 2,585 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,770 ms
コンパイル使用メモリ 390,976 KB
実行使用メモリ 9,868 KB
最終ジャッジ日時 2026-10-08 00:35:41
合計ジャッジ時間 7,232 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;

using mint=modint;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

#line 2 "string/manacher.hpp"

#include <vector>
using namespace std;

template <typename Container>
vector<int> manacher(const Container& S) {
  vector<int> res(S.size());
  int i = 0, j = 0;
  while (i < int(S.size())) {
    while (i - j >= 0 and i + j < int(S.size()) and S[i - j] == S[i + j]) j++;
    res[i] = j;
    int k = 1;
    while (i - k >= 0 and i + k < int(S.size()) and k + res[i - k] < j)
      res[i + k] = res[i - k], k++;
    i += k, j -= k;
  }
  return res;
}

// 中心軸を固定したときの各軸に対して極大な回文を左から列挙(空文字列を含む)
template <typename Container>
vector<pair<int, int>> enumerate_palindromes(const Container& vec) {
  using T = typename Container::value_type;
  vector<T> v;
  const int N = vec.size();
  for (int i = 0; i < N - 1; i++) {
    v.push_back(vec[i]);
    v.push_back(-1);
  }
  v.push_back(vec.back());
  const auto man = manacher(v);
  vector<pair<int, int>> ret;
  for (int i = 0; i < N * 2 - 1; i++) {
    if (i & 1) {
      int w = man[i] / 2;
      ret.emplace_back((i + 1) / 2 - w, (i + 1) / 2 + w);
    } else {
      int w = (man[i] - 1) / 2;
      ret.emplace_back(i / 2 - w, i / 2 + w + 1);
    }
  }
  return ret;
}

// ret[r] : s[l, r] が回文である最小の l
template <typename Container>
vector<int> enumerate_leftmost_palindromes(const Container& vec) {
  vector<int> v(vec.size(), 1);
  for (auto& [l, r] : enumerate_palindromes(vec)) {
    v[r - 1] = max(v[r - 1], r - l);
  }
  for (int i = (int)vec.size() - 2; i >= 0; i--) v[i] = max(v[i], v[i + 1] - 2);
  vector<int> ret(vec.size());
  for (int i = 0; i < (int)vec.size(); i++) ret[i] = i + 1 - v[i];
  return ret;
}

/**
 * @brief Manacher's algorithm
 */

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

  string S;
  cin>>S;
  auto pal=enumerate_palindromes(S);
  int ans=1;
  for(auto [l,r]:pal){
    int len=r-l;
    if(len==sz(S))len-=2;
    ans=max(ans,len);
  }
  cout<<ans<<'\n';

}
0