結果

問題 No.765 ukuku 2
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:44:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,309 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 87,296 KB
最終ジャッジ日時 2025-06-12 21:48:49
合計ジャッジ時間 6,997 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 18 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_lps(s):
    # Manacher's algorithm to find the maximum LPS length
    transformed = '#' + '#'.join(s) + '#'
    n = len(transformed)
    P = [0] * n
    C = R = 0
    max_len = 0
    for i in range(n):
        mirror = 2*C - i
        if i < R:
            P[i] = min(R - i, P[mirror])
        a, b = i + (1 + P[i]), i - (1 + P[i])
        while a < n and b >= 0 and transformed[a] == transformed[b]:
            P[i] += 1
            a += 1
            b -= 1
        if i + P[i] > R:
            C = i
            R = i + P[i]
        max_len = max(max_len, P[i])
    return max_len

def main():
    import sys
    s = sys.stdin.readline().strip()
    n = len(s)
    if n == 0:
        print(0)
        return
    # Compute the maximum LPS
    max_lps = compute_lps(s)
    # Compute M: maximum expansion by deleting one character
    max_m = 0
    for i in range(n):
        left = i - 1
        right = i + 1
        cnt = 0
        while left >= 0 and right < n and s[left] == s[right]:
            cnt += 1
            left -= 1
            right += 1
        current_m = cnt * 2
        if current_m > max_m:
            max_m = current_m
    # Determine the answer
    if max_lps == n:
        print(n - 1)
    else:
        print(max(max_lps, max_m))

if __name__ == "__main__":
    main()
0