結果
問題 |
No.765 ukuku 2
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()