結果

問題 No.263 Common Palindromes Extra
ユーザー qwewe
提出日時 2025-04-24 12:27:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,134 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 573,100 KB
最終ジャッジ日時 2025-04-24 12:28:57
合計ジャッジ時間 11,447 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 3 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    S = sys.stdin.readline().strip()
    T = sys.stdin.readline().strip()

    # Precompute pow_base arrays for two different hashes
    base1 = 911382629
    mod1 = 10**18 + 3
    base2 = 3571428571
    mod2 = 10**18 + 7
    max_pow = 2 * 500000 + 10  # Sufficiently large to cover max possible palindrome length

    pow1 = [1] * (max_pow + 1)
    pow2 = [1] * (max_pow + 1)
    for i in range(1, max_pow + 1):
        pow1[i] = (pow1[i-1] * base1) % mod1
        pow2[i] = (pow2[i-1] * base2) % mod2

    def build_pal_tree(s):
        tree = []
        # Initialize with two root nodes: odd (0) and even (1)
        tree.append({'len': -1, 'fail': 0, 'next': defaultdict(int), 'h1': 0, 'h2': 0, 'cnt': 0})  # Odd root
        tree.append({'len': 0, 'fail': 0, 'next': defaultdict(int), 'h1': 0, 'h2': 0, 'cnt': 0})   # Even root
        last = 1  # Initially points to even root
        s_arr = list(s)
        for i in range(len(s_arr)):
            c = s_arr[i]
            current = last
            # Find the current node to expand
            while True:
                curr_len = tree[current]['len']
                # Calculate the position to check
                pos = i - curr_len - 1
                if pos >= 0 and s_arr[pos] == c:
                    break
                current = tree[current]['fail']
            # Check if the child exists
            if tree[current]['next'][c] != 0:
                last = tree[current]['next'][c]
                tree[last]['cnt'] += 1
                continue
            # Create new node
            new_node = {
                'len': tree[current]['len'] + 2,
                'fail': 0,
                'next': defaultdict(int),
                'h1': 0,
                'h2': 0,
                'cnt': 1
            }
            # Calculate hash values
            if current == 0:  # Parent is odd root
                new_h1 = ord(c)
                new_h2 = ord(c)
            else:
                p_len = tree[current]['len']
                new_h1 = (ord(c) * pow1[p_len + 1] + tree[current]['h1'] * base1 + ord(c)) % mod1
                new_h2 = (ord(c) * pow2[p_len + 1] + tree[current]['h2'] * base2 + ord(c)) % mod2
            new_node['h1'] = new_h1
            new_node['h2'] = new_h2
            tree.append(new_node)
            new_node_idx = len(tree) - 1
            tree[current]['next'][c] = new_node_idx
            # Set fail for the new node
            if new_node['len'] == 1:
                new_node['fail'] = 1
            else:
                # Find the fail node
                fail_current = tree[current]['fail']
                while True:
                    flen = tree[fail_current]['len']
                    pos = i - flen - 1
                    if pos >= 0 and s_arr[pos] == c:
                        if tree[fail_current]['next'][c] != 0:
                            new_node['fail'] = tree[fail_current]['next'][c]
                            break
                        else:
                            fail_current = tree[fail_current]['fail']
                    else:
                        fail_current = tree[fail_current]['fail']
            last = new_node_idx
        # Accumulate counts
        nodes_order = sorted(range(len(tree)), key=lambda x: -tree[x]['len'])
        for node_idx in nodes_order:
            if node_idx <= 1:
                continue  # Skip roots
            fail_idx = tree[node_idx]['fail']
            if fail_idx >= 0 and fail_idx < len(tree):
                tree[fail_idx]['cnt'] += tree[node_idx]['cnt']
        # Build hash map
        hash_map = defaultdict(int)
        for node in tree:
            if node['len'] <= 0:
                continue
            h = (node['h1'], node['h2'])
            hash_map[h] += node['cnt']
        return hash_map

    s_hash = build_pal_tree(S)
    t_hash = build_pal_tree(T)

    result = 0
    for h, cnt_s in s_hash.items():
        cnt_t = t_hash.get(h, 0)
        if cnt_t > 0:
            result += cnt_s * cnt_t
    print(result)

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