結果

問題 No.2234 palindromer
コンテスト
ユーザー srjywrdnprkt
提出日時 2023-08-27 01:38:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,986 bytes
コンパイル時間 1,922 ms
コンパイル使用メモリ 196,340 KB
最終ジャッジ日時 2025-02-16 14:57:13
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename T>
vector<int> z_algorithm(T &S){
    vector<int> Z(S.size());
    Z[0] = S.size();
    int i=1, j=0;
    while(i < S.size()){
        while(i+j < S.size() && S[j] == S[i+j]) j++;
        Z[i] = j;

        if (j == 0){
            i++;
            continue;
        }
        int k=1;
        while(k < j && k + Z[k] < j){
            Z[i+k] = Z[k];
            k++;
        }
        i += k;
        j -= k;
    }

    return Z;
}

//M[2n]...n文字目を中心とする最長回文
//M[2n+1]...n文字目とn+1文字目を中心とする最長回文
template <typename T>
vector<int> manacher(T &s){
    string S="";
    for (auto x : s){
        S += x;
        S += '$';
    }
    S.pop_back();
    vector<int> R(S.size());
    int i=0, j=0;
    while(i < S.size()){
        while(i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) j++;
        R[i] = j;
        int k=1;
        while(i-k >= 0 && k + R[i-k] < j){
            R[i+k] = R[i-k];
            k++;
        }
        i += k;
        j -= k;
    }

    for (int i=0; i<S.size(); i++){
        if (i % 2 == R[i] % 2) R[i]--;
    }

    return R;
}

int main(){

    string S, T;
    cin >> S;
    int N=S.size(), mx=0, r;
    vector<int> R = manacher(S);
    for (int i=2*N-2; i>=N-1; i--) mx = max(mx, R[i]);
    for (int i=2*N-2; i>=N-1; i--){
        if (mx == R[i]){
            //奇数長
            if (i % 2 == 0){
                r = (R[i]-1)/2;
                i /= 2;
                T = S.substr(0, i-r);
                reverse(T.begin(), T.end());
                cout << S << T << endl;
                return 0;
            }
            //偶数長
            else{
                r = R[i]/2;
                i /= 2;
                T = S.substr(0, i-r+1);
                reverse(T.begin(), T.end());
                cout << S << T << endl;
                return 0;
            }
        }
    }

    return 0;
}
0