結果

問題 No.765 ukuku 2
ユーザー gew1fw
提出日時 2025-06-12 14:16:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,073 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 81,644 KB
最終ジャッジ日時 2025-06-12 14:16:38
合計ジャッジ時間 3,734 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def manacher(s):
    # Preprocess the string to handle even and odd length palindromes uniformly
    T = '#'.join('^{}$'.format(s))
    n = len(T)
    P = [0] * n  # Array to store the length of the palindrome centered at each position
    C = R = 0    # Center and right boundary of the current palindrome
    max_len = 0  # Maximum length of the palindrome found

    for i in range(1, n - 1):
        # Mirror of i with respect to C
        mirror = 2 * C - i

        # Check if the current position is within the right boundary
        if i < R:
            P[i] = min(R - i, P[mirror])

        # Expand around the current center
        while T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1

        # Update the center and right boundary if the expanded palindrome exceeds the current boundary
        if i + P[i] > R:
            C, R = i, i + P[i]

        # Update the maximum length found
        if P[i] > max_len:
            max_len = P[i]

    return max_len

s = input().strip()
if s == s[::-1]:
    print(len(s) - 1)
else:
    print(manacher(s))
0