結果

問題 No.765 ukuku 2
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:21:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,336 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 85,664 KB
最終ジャッジ日時 2025-06-12 19:22:23
合計ジャッジ時間 18,154 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def manachers(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    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 t[a] == t[b]:
            p[i] += 1
            a += 1
            b -= 1
        if i + p[i] > r:
            c = i
            r = i + p[i]
        if p[i] > max_len:
            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
    
    L = manachers(S)
    
    mod = 10**18 + 3
    base = 911382629
    
    # Precompute prefix hashes for S
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + ord(S[i])) % mod
        power[i+1] = (power[i] * base) % mod
    
    # Precompute prefix hashes for reversed S
    R = S[::-1]
    prefix_hash_rev = [0] * (n + 1)
    for i in range(n):
        prefix_hash_rev[i+1] = (prefix_hash_rev[i] * base + ord(R[i])) % mod
    
    max_expand = 0
    for i in range(n):
        low = 0
        high = min(i, (n-1) - i)
        best_l = 0
        while low <= high:
            mid = (low + high) // 2
            if mid == 0:
                best_l = 0
                low = mid + 1
                continue
            a = n - i
            b = a + mid - 1
            if b >= len(R):
                valid = False
            else:
                hash_rev_left = (prefix_hash_rev[b + 1] - prefix_hash_rev[a] * power[mid]) % mod
            right_start = i + 1
            right_end = i + 1 + mid - 1
            if right_end >= n:
                valid = False
            else:
                hash_right = (prefix_hash[right_end + 1] - prefix_hash[right_start] * power[mid]) % mod
            if a <= len(R) and right_end < n and hash_rev_left == hash_right:
                best_l = mid
                low = mid + 1
            else:
                high = mid - 1
        if best_l > max_expand:
            max_expand = best_l
    M = max_expand * 2
    
    if L == n:
        answer = max(L - 1, M)
    else:
        answer = max(L, M)
    print(answer)

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