結果

問題 No.263 Common Palindromes Extra
ユーザー qwewe
提出日時 2025-04-24 12:21:26
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,176 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 536,324 KB
最終ジャッジ日時 2025-04-24 12:23:29
合計ジャッジ時間 9,426 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 TLE * 2 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 10**18 + 3
BASE = 911382629

class Node:
    __slots__ = ['length', 'suffix_link', 'transitions', 'hash', 'cnt']
    def __init__(self, length, suffix_link):
        self.length = length
        self.suffix_link = suffix_link
        self.transitions = {}
        self.hash = 0
        self.cnt = 0

def precompute_powers(max_len, base, mod):
    pow = [1] * (max_len + 2)
    for i in range(1, max_len + 2):
        pow[i] = (pow[i-1] * base) % mod
    return pow

def build_eertree(s, pow_table, base, mod):
    root_neg = Node(-1, None)
    root_neg.suffix_link = root_neg
    root_0 = Node(0, root_neg)
    root_0.suffix_link = root_neg
    nodes = [root_neg, root_0]
    last = root_0
    s_list = list(s)
    for idx in range(len(s_list)):
        c = s_list[idx]
        current = last
        while True:
            candidate = current
            clen = candidate.length
            pos = idx - clen - 1
            if pos >= 0 and s_list[pos] == c:
                break
            current = current.suffix_link
        if c in current.transitions:
            last = current.transitions[c]
            last.cnt += 1
            continue
        new_node = Node(current.length + 2, None)
        nodes.append(new_node)
        if new_node.length == 1:
            new_node.suffix_link = root_0
        else:
            suffix = current.suffix_link
            while True:
                clen_suffix = suffix.length
                pos_suffix = idx - clen_suffix - 1
                if pos_suffix >= 0 and s_list[pos_suffix] == c and c in suffix.transitions:
                    new_node.suffix_link = suffix.transitions[c]
                    break
                if suffix.length == -1:
                    new_node.suffix_link = root_0
                    break
                suffix = suffix.suffix_link
        if current.length == -1:
            new_node.hash = ord(c) % mod
        elif current.length == 0:
            new_node.hash = (ord(c) * base + ord(c)) % mod
        else:
            new_node.hash = (ord(c) * pow_table[current.length + 1] + current.hash * base + ord(c)) % mod
        current.transitions[c] = new_node
        last = new_node
        last.cnt = 1
    nodes_sorted = sorted(nodes[2:], key=lambda x: -x.length)
    for node in nodes_sorted:
        if node.suffix_link:
            node.suffix_link.cnt += node.cnt
    hash_map = {}
    for node in nodes:
        if node.length > 0:
            h = node.hash
            cnt = node.cnt
            if h in hash_map:
                hash_map[h] += cnt
            else:
                hash_map[h] = cnt
    return hash_map

def main():
    s = sys.stdin.readline().strip()
    t = sys.stdin.readline().strip()
    max_len_s = len(s) * 2 + 2
    max_len_t = len(t) * 2 + 2
    pow_s = precompute_powers(max_len_s, BASE, MOD)
    pow_t = precompute_powers(max_len_t, BASE, MOD)
    hash_map_s = build_eertree(s, pow_s, BASE, MOD)
    hash_map_t = build_eertree(t, pow_t, BASE, MOD)
    result = 0
    for h, cnt_s in hash_map_s.items():
        cnt_t = hash_map_t.get(h, 0)
        result += cnt_s * cnt_t
    print(result)

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