結果

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

ソースコード

diff # 

def manacher(s):
    t = '#'.join('^{}$'.format(s))
    n = len(t)
    p = [0] * n
    C = R = 0
    max_len = 0
    for i in range(1, n - 1):
        mirror = 2 * C - i
        if i < R:
            p[i] = min(R - i, p[mirror])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > R:
            C = i
            R = i + p[i]
        max_len = max(max_len, p[i])
    return max_len

def main():
    S = input().strip()
    n = len(S)
    if n == 0:
        print(0)
        return
    
    # Precompute hashes for forward and backward strings
    base = 911382629
    mod = 10**18 + 3
    pow_base = [1] * (n + 1)
    hash_forward = [0] * (n + 1)
    for i in range(n):
        hash_forward[i+1] = (hash_forward[i] * base + ord(S[i])) % mod
        pow_base[i+1] = (pow_base[i] * base) % mod
    
    S_rev = S[::-1]
    hash_backward = [0] * (n + 1)
    for i in range(n):
        hash_backward[i+1] = (hash_backward[i] * base + ord(S_rev[i])) % mod
    
    L = manacher(S)
    
    max_M = 0
    for k in range(n):
        max_possible_l = min(k, n - 1 - k)
        if max_possible_l == 0:
            continue
        low, high = 0, max_possible_l
        best_l = 0
        while low <= high:
            mid = (low + high) // 2
            if mid == 0:
                best_l = 0
                low = mid + 1
                continue
            left_start = k - mid
            left_end = k - 1
            if left_start < 0:
                high = mid - 1
                continue
            # Compute hash for left substring
            hash_left = (hash_forward[left_end + 1] - hash_forward[left_start] * pow_base[mid]) % mod
            # Compute hash for reversed right substring
            a = (n - 1) - (k + mid)
            if a < 0:
                high = mid - 1
                continue
            # Check if a + mid exceeds the hash_backward array
            if a + mid > n:
                high = mid - 1
                continue
            hash_right_rev = (hash_backward[a + mid] - hash_backward[a] * pow_base[mid]) % mod
            if hash_left == hash_right_rev:
                best_l = mid
                low = mid + 1
            else:
                high = mid - 1
        max_M = max(max_M, best_l)
    M = 2 * max_M
    
    if L < n:
        ans = max(L, M)
    else:
        ans = max(L - 1, M)
    print(ans)

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