結果
| 問題 |
No.263 Common Palindromes Extra
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:21:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,594 bytes |
| コンパイル時間 | 263 ms |
| コンパイル使用メモリ | 82,688 KB |
| 実行使用メモリ | 404,944 KB |
| 最終ジャッジ日時 | 2025-05-14 13:24:04 |
| 合計ジャッジ時間 | 6,238 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 5 MLE * 7 |
ソースコード
import sys
import array
def solve():
S_str = sys.stdin.readline().strip()
T_str = sys.stdin.readline().strip()
S_codes = [ord(c) - ord('A') for c in S_str]
T_codes = [ord(c) - ord('A') for c in T_str]
MAX_S_LEN = len(S_codes)
MAX_T_LEN = len(T_codes)
# Based on constraints 1 <= len(S), len(T), this check is not strictly needed
# but good for robustness if constraints were different.
if MAX_S_LEN == 0 or MAX_T_LEN == 0:
sys.stdout.write("0\n")
return
# Max possible nodes: initial 2 + len(S) + len(T)
Max_N_nodes = MAX_S_LEN + MAX_T_LEN + 2
# s_arr needs to hold the longer of S or T, plus one for sentinel at index 0.
s_arr_capacity = max(MAX_S_LEN, MAX_T_LEN) + 1
node_len = array.array('i', [0] * Max_N_nodes) # 'i' for signed int (usually 4 bytes)
node_link = array.array('i', [0] * Max_N_nodes)
# For node_next, using a flattened array: node_next_flat[node_idx * 26 + char_code]
node_next_flat = array.array('i', [0] * (Max_N_nodes * 26))
# Counts can be large, and their product even larger. Total sum up to 10^18 needs 64-bit int.
# array.array type 'q' is for signed long long (usually 8 bytes).
count_s_raw = array.array('q', [0] * Max_N_nodes)
count_t_raw = array.array('q', [0] * Max_N_nodes)
# s_arr stores characters of the string currently being processed.
# 'b' for signed char, allows sentinel -1 and char codes 0-25.
s_arr = array.array('b', [0] * s_arr_capacity)
# Eertree Initialization
# Node 0: empty string palindrome, len 0
node_len[0] = 0
node_link[0] = 1 # Suffix link of empty string node is node 1
# Node 1: imaginary palindrome, len -1
node_len[1] = -1
node_link[1] = 1 # Node 1 links to itself (or any fixed node, often 1)
# Eertree state variables, grouped in a dictionary for convenience
eertree_state = {
's_current_len': 0, # Number of chars in s_arr (indices 1 to s_current_len)
'suff_node_idx': 1, # Current longest palindromic suffix node. Initialized to 1 for a new string.
'num_active_nodes': 2 # Nodes 0 and 1 initially exist
}
s_arr[0] = -1 # Sentinel char_code, different from A-Z (0-25)
# Helper functions for node_next_flat access
def get_next(u_idx, char_code):
return node_next_flat[u_idx * 26 + char_code]
def set_next(u_idx, char_code, v_idx):
node_next_flat[u_idx * 26 + char_code] = v_idx
def add_char_to_eertree(char_code, is_s_string_flag):
# Update current string length and add char to s_arr
s_cur_len_val = eertree_state['s_current_len'] + 1
eertree_state['s_current_len'] = s_cur_len_val
s_arr[s_cur_len_val] = char_code
# Find parent P of the new palindrome cPc
# Start from suff_node_idx (longest palindromic suffix of string_so_far_before_current_char)
cur_processing_node = eertree_state['suff_node_idx']
while True:
# Check if s_arr[s_cur_len_val - len[P] - 1] == s_arr[s_cur_len_val]
# This means char_before_P == current_char
# This loop is guaranteed to terminate because node 1 (len -1) will eventually be reached.
# For node 1 (len -1), index is s_cur_len_val - (-1) - 1 = s_cur_len_val.
# So s_arr[s_cur_len_val] == s_arr[s_cur_len_val] is true.
if s_arr[s_cur_len_val - node_len[cur_processing_node] - 1] == s_arr[s_cur_len_val]:
break
cur_processing_node = node_link[cur_processing_node]
# If palindrome cPc (node next[P][c]) doesn't exist, create it
if get_next(cur_processing_node, char_code) == 0:
new_node_idx = eertree_state['num_active_nodes']
eertree_state['num_active_nodes'] += 1
set_next(cur_processing_node, char_code, new_node_idx)
node_len[new_node_idx] = node_len[cur_processing_node] + 2
# Determine suffix link for new_node_idx
if node_len[new_node_idx] == 1: # Single char palindrome
node_link[new_node_idx] = 0 # Suffix link is empty string node
else:
# Traverse from link[P] to find Q, such that link[cPc] = cQc
temp_link_search_node = node_link[cur_processing_node]
while True:
if s_arr[s_cur_len_val - node_len[temp_link_search_node] - 1] == s_arr[s_cur_len_val]:
break
temp_link_search_node = node_link[temp_link_search_node]
node_link[new_node_idx] = get_next(temp_link_search_node, char_code)
eertree_state['suff_node_idx'] = new_node_idx
else: # Palindrome cPc already exists
eertree_state['suff_node_idx'] = get_next(cur_processing_node, char_code)
# Increment raw count for the palindrome that is the longest suffix ending at current position
current_longest_pal_node = eertree_state['suff_node_idx']
if is_s_string_flag:
count_s_raw[current_longest_pal_node] += 1
else:
count_t_raw[current_longest_pal_node] += 1
# Process string S
eertree_state['s_current_len'] = 0 # Reset for string S (empty)
eertree_state['suff_node_idx'] = 1 # Current longest palindromic suffix is node 1 (len -1)
for code in S_codes:
add_char_to_eertree(code, True)
# Process string T
eertree_state['s_current_len'] = 0 # Reset for string T (empty)
eertree_state['suff_node_idx'] = 1 # Current longest palindromic suffix is node 1 (len -1)
for code in T_codes:
add_char_to_eertree(code, False)
current_total_nodes = eertree_state['num_active_nodes']
# Accumulate counts up the suffix links. Iterate from longest to shortest palindromes
# (approximated by iterating node indices in decreasing order, as nodes are added incrementally).
# Nodes 0 and 1 are special roots, actual palindromes start from index 2.
for i in range(current_total_nodes - 1, 1, -1): # Iterate from (num_active_nodes-1) down to 2
link_of_i = node_link[i]
count_s_raw[link_of_i] += count_s_raw[i]
count_t_raw[link_of_i] += count_t_raw[i]
# Calculate final answer
total_common_score = 0
# Iterate over all actual palindrome nodes (indices 2 to current_total_nodes-1)
for i in range(2, current_total_nodes):
total_common_score += count_s_raw[i] * count_t_raw[i]
sys.stdout.write(str(total_common_score) + "\n")
solve()