結果

問題 No.765 ukuku 2
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:26:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,932 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 147,868 KB
最終ジャッジ日時 2025-04-24 12:27:34
合計ジャッジ時間 7,442 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 20 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def manacher(s):
    if not s:
        return []
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    c = r = 0
    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        a, b = i + p[i] + 1, i - p[i] - 1
        while a < n and b >= 0 and t[a] == t[b]:
            p[i] += 1
            a += 1
            b -= 1
        if i + p[i] > r:
            c = i
            r = i + p[i]
    return p

s = input().strip()
n = len(s)
if n < 2:
    print(0)
    exit()

p = manacher(s)

left_events = [[] for _ in range(n)]
right_events = [[] for _ in range(n)]

for i in range(len(p)):
    radius = p[i]
    if radius == 0:
        continue
    original_left = (i - radius + 1) // 2
    original_right = (i + radius - 1 - 1) // 2
    if original_left < 0 or original_right >= n:
        continue
    length = original_right - original_left + 1
    if original_right < n:
        left_events[original_right].append(length)
    if original_left >= 0:
        right_events[original_left].append(length)

left_max = [0] * n
current_max = 0
for i in range(n):
    for l in left_events[i]:
        current_max = max(current_max, l)
    left_max[i] = current_max

right_max = [0] * n
current_max = 0
for i in range(n-1, -1, -1):
    for l in right_events[i]:
        current_max = max(current_max, l)
    right_max[i] = current_max

max_result = 0
for i in range(n):
    current = 0
    if i > 0:
        current = max(current, left_max[i-1])
    if i < n-1:
        current = max(current, right_max[i+1])
    if i > 0 and i < n-1 and s[i-1] == s[i+1]:
        l_ptr = i-1
        r_ptr = i+1
        length = 2
        while l_ptr - 1 >= 0 and r_ptr + 1 < n and s[l_ptr-1] == s[r_ptr+1]:
            l_ptr -= 1
            r_ptr += 1
            length += 2
        current = max(current, length)
    if current > max_result:
        max_result = current

print(max_result)
0