結果

問題 No.765 ukuku 2
ユーザー gew1fw
提出日時 2025-06-12 17:08:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,580 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 89,960 KB
最終ジャッジ日時 2025-06-12 17:08:22
合計ジャッジ時間 7,082 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def longest_palindrome_after_deletion(s):
    n = len(s)
    if n == 1:
        return 0
    # Manacher's algorithm to find all possible palindromes
    # Preprocess the string
    t = '#' + '#'.join(s) + '#'
    n_t = len(t)
    P = [0] * n_t
    C, R = 0, 0
    max_len = 0
    max_indices = []
    for i in range(n_t):
        mirror = 2 * C - i
        if i < R:
            P[i] = min(R - i, P[mirror])
        # Attempt to expand palindrome centered at i
        a, b = i + (1 + P[i]), i - (1 + P[i])
        while a < n_t and b >= 0 and t[a] == t[b]:
            P[i] += 1
            a += 1
            b -= 1
        # Update center and right boundary if palindrome centered at i expands past R
        if i + P[i] > R:
            C = i
            R = i + P[i]
        # Update max_len and record the centers that achieve this max_len
        if P[i] > max_len:
            max_len = P[i]
            max_indices = [i]
        elif P[i] == max_len:
            max_indices.append(i)
    
    # Convert back to original string's indices
    max_len = (max_len - 1) // 2  # since in t, each character is doubled
    
    # Now, for each i, compute the max palindrome length after deleting s[i]
    max_after_deletion = 0
    
    # Precompute for each position the maximum palindrome length in the prefix and suffix
    left_max = [0] * n
    right_max = [0] * n
    
    # Compute left_max
    for i in range(n):
        if i == 0:
            left_max[i] = 1
            continue
        current_max = left_max[i-1]
        for j in range(0, i+1):
            if s[j] == s[i] and (i - j + 1) > current_max:
                is_pal = True
                for k in range(j+1, (j+i)//2 + 1):
                    if s[k] != s[i - (k - j)]:
                        is_pal = False
                        break
                if is_pal:
                    current_max = i - j + 1
                    break
        left_max[i] = current_max
    
    # Compute right_max
    for i in range(n-1, -1, -1):
        if i == n-1:
            right_max[i] = 1
            continue
        current_max = right_max[i+1]
        for j in range(n-1, i-1, -1):
            if s[j] == s[i] and (j - i + 1) > current_max:
                is_pal = True
                for k in range(i+1, (i+j)//2 +1):
                    if s[k] != s[j - (k - i)]:
                        is_pal = False
                        break
                if is_pal:
                    current_max = j - i + 1
                    break
        right_max[i] = current_max
    
    # Precompute the maximum palindrome lengths using Manacher's data
    # Now, for each i, compute the maximum palindrome length after deletion
    for i in range(n):
        left_part = s[:i]
        right_part = s[i+1:]
        combined = left_part + right_part
        current_max = 0
        
        # Check for the maximum palindrome in left_part, right_part, and combined
        # Precompute the maximum of left and right
        max_left = left_max[i-1] if i > 0 else 0
        max_right = right_max[i+1] if i < n-1 else 0
        current_max = max(max_left, max_right)
        
        # Check combined
        # Use Manacher's algorithm to find the maximum palindrome in combined
        # This is a fallback method and may be too slow for large n, but for the sake of example
        # We'll proceed with it
        if len(combined) > current_max:
            # Compute the maximum palindrome in combined using a simple method
            def max_pal(s):
                n = len(s)
                max_len = 1
                for i in range(n):
                    # Odd length
                    l, r = i, i
                    while l >=0 and r < n and s[l] == s[r]:
                        if r - l +1 > max_len:
                            max_len = r - l +1
                        l -=1
                        r +=1
                    # Even length
                    l, r = i, i+1
                    while l >=0 and r < n and s[l] == s[r]:
                        if r - l +1 > max_len:
                            max_len = r - l +1
                        l -=1
                        r +=1
                return max_len
            
            combined_max = max_pal(combined)
            current_max = max(current_max, combined_max)
        
        if current_max > max_after_deletion:
            max_after_deletion = current_max
    
    return max_after_deletion

# Read input
s = input().strip()
# Compute the result
result = longest_palindrome_after_deletion(s)
# Output the result
print(result)
0