結果

問題 No.765 ukuku 2
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:05:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,153 bytes
コンパイル時間 470 ms
コンパイル使用メモリ 81,844 KB
実行使用メモリ 86,268 KB
最終ジャッジ日時 2025-04-09 21:07:48
合計ジャッジ時間 25,973 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    S = sys.stdin.readline().strip()
    N = len(S)
    if N <= 1:
        print(1 if N == 1 else 0)
        return
    
    # Manacher's algorithm to find the maximum palindrome length and its range
    max_len, max_L, max_R = 0, 0, 0
    s = '#' + '#'.join(S) + '#'
    n = len(s)
    P = [0] * n
    C, R = 0, 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 s[a] == s[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]
            center = i
    original_L = max_len
    max_L = (center - max_len) // 2
    max_R = (center + max_len) // 2 - 1
    
    # Precompute prefix and suffix hashes with rolling hash
    base = 911382629
    mod = 10**18 + 3
    prefix = [0] * (N+1)
    power = [1] * (N+1)
    for i in range(N):
        prefix[i+1] = (prefix[i] * base + ord(S[i])) % mod
        power[i+1] = (power[i] * base) % mod
    
    suffix = [0] * (N+2)
    for i in range(N, 0, -1):
        suffix[i] = (suffix[i+1] * base + ord(S[i-1])) % mod
    
    def get_prefix_hash(l, r):
        return (prefix[r+1] - prefix[l] * power[r - l + 1]) % mod
    
    def get_suffix_hash(l, r):
        return (suffix[l+1] - suffix[r+2] * power[r - l + 1]) % mod
    
    max_result = 0
    for i in range(N):
        current_max = 0
        if max_L <= i <= max_R:
            current_max = original_L - 1
        else:
            current_max = original_L
        
        l, r = i-1, i+1
        if l >= 0 and r < N:
            if S[l] == S[r]:
                low = 0
                high = min(l, N-1 - r)
                best_k = 0
                while low <= high:
                    mid = (low + high) // 2
                    a = l - mid
                    b = r + mid
                    if a < 0 or b >= N:
                        high = mid - 1
                        continue
                    hash1 = get_prefix_hash(a, l)
                    hash2 = get_suffix_hash(r, b)
                    if hash1 == hash2:
                        best_k = mid
                        low = mid + 1
                    else:
                        high = mid - 1
                odd_length = best_k * 2 + 1
                current_max = max(current_max, odd_length)
        
        if i > 0 and S[i-1] == S[i]:
            center = i-1
            length = 1
            low = 0
            high = min(center, N-1 - (i))
            best_k = 0
            while low <= high:
                mid = (low + high) // 2
                a = center - mid
                b = i + mid
                if a < 0 or b >= N:
                    high = mid - 1
                    continue
                hash1 = get_prefix_hash(a, center)
                hash2 = get_suffix_hash(i, b)
                if hash1 == hash2:
                    best_k = mid
                    low = mid + 1
                else:
                    high = mid - 1
            even_length = best_k * 2 + 2
            current_max = max(current_max, even_length)
        
        if i < N-1 and S[i] == S[i+1]:
            center = i
            length = 1
            low = 0
            high = min(center, N-1 - (i+1))
            best_k = 0
            while low <= high:
                mid = (low + high) // 2
                a = center - mid
                b = (i+1) + mid
                if a < 0 or b >= N:
                    high = mid - 1
                    continue
                hash1 = get_prefix_hash(a, center)
                hash2 = get_suffix_hash(i+1, b)
                if hash1 == hash2:
                    best_k = mid
                    low = mid + 1
                else:
                    high = mid - 1
            even_length = best_k * 2 + 2
            current_max = max(current_max, even_length)
        
        if current_max > max_result:
            max_result = current_max
    
    print(max_result)

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