結果

問題 No.765 ukuku 2
ユーザー qwewe
提出日時 2025-05-14 13:25:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,380 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 69,888 KB
最終ジャッジ日時 2025-05-14 13:27:14
合計ジャッジ時間 6,779 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def get_manacher_lps_length(s_orig):
    if not s_orig:
        return 0
    
    # Transform s_orig to s_manacher: "aba" -> "#a#b#a#"
    # This handles odd and even length palindromes uniformly.
    s_manacher = "#" + "#".join(list(s_orig)) + "#"
    
    n_manacher = len(s_manacher)
    # p[i] = radius of the palindrome centered at s_manacher[i].
    # The length of this palindrome in s_orig is p[i].
    p = [0] * n_manacher 
    
    center = 0  # Center of the rightmost palindrome found so far
    right_boundary = 0  # Right boundary of this palindrome (exclusive: S[C-P[C]...C+P[C]])
                        # More accurately, R = C + P[C]
    
    max_lps_len_s_orig = 0
    
    for i in range(n_manacher):
        # Calculate mirror index for i with respect to center
        mirror = 2 * center - i
        
        # If i is within the current right_boundary, p[i] can be initialized
        # based on p[mirror].
        if i < right_boundary:
            p[i] = min(right_boundary - i, p[mirror])
        # else: p[i] is 0 (already initialized)
        
        # Attempt to expand palindrome centered at i
        # Check elements S_manacher[i + (p[i] + 1)] vs S_manacher[i - (p[i] + 1)]
        # Indices for expansion:
        #   left_char_idx = i - (p[i] + 1)
        #   right_char_idx = i + (p[i] + 1)
        # Valid as long as left_char_idx >= 0 and right_char_idx < n_manacher
        
        # Corrected expansion loop condition from common implementations:
        # New potential radius is p[i]+1. Characters to check are at s_manacher[i - (p[i]+1)] and s_manacher[i + (p[i]+1)].
        # The current palindrome is s_manacher[i-p[i] ... i+p[i]].
        # We try to extend it by checking s_manacher[i-p[i]-1] and s_manacher[i+p[i]+1].
        
        a = i + (p[i] + 1) # right char to check
        b = i - (p[i] + 1) # left char to check

        while b >= 0 and a < n_manacher and s_manacher[a] == s_manacher[b]:
            p[i] += 1
            a += 1
            b -= 1
            
        # If palindrome centered at i expands past right_boundary,
        # adjust center and right_boundary
        if i + p[i] > right_boundary:
            center = i
            right_boundary = i + p[i]
            
        max_lps_len_s_orig = max(max_lps_len_s_orig, p[i])
            
    return max_lps_len_s_orig

def solve():
    s = sys.stdin.readline().strip()
    n = len(s)
    
    # Constraints: 2 <= |S| <= 2 * 10^5
    # If |S|=2, say "ab".
    #   Delete 'a': s_prime="b", LPS("b")=1.
    #   Delete 'b': s_prime="a", LPS("a")=1.
    #   Max tapisa = 1.
    # The Manacher function should handle single character strings correctly (LPS=1).

    max_overall_tapisa = 0
    
    if n == 0: # Should not happen based on constraints
        print(0)
        return

    for i in range(n):
        # Create string S' by deleting S[i]
        s_prime = s[:i] + s[i+1:]
        
        # If s_prime becomes empty (only if original S had 1 char, which is ruled out by constraints)
        # or if original S had 2 chars, s_prime has 1 char.
        if not s_prime: 
            current_tapisa = 0
        else:
            current_tapisa = get_manacher_lps_length(s_prime)
        
        max_overall_tapisa = max(max_overall_tapisa, current_tapisa)
        
    print(max_overall_tapisa)

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