結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    S = sys.stdin.readline().strip()
    T = sys.stdin.readline().strip()

    # Precompute powers for two different bases and mods
    max_len = max(len(S), len(T)) + 2
    base1 = 911382629
    base2 = 3571428571
    mod1 = 10**18 + 3
    mod2 = 10**18 + 7

    # Precompute power arrays
    power1 = [1] * (max_len + 2)
    power2 = [1] * (max_len + 2)
    for i in range(1, max_len + 2):
        power1[i] = (power1[i-1] * base1) % mod1
        power2[i] = (power2[i-1] * base2) % mod2

    class Node:
        __slots__ = ['length', 'hash1', 'hash2', 'count', 'suffix_link', 'transitions']
        def __init__(self):
            self.length = 0
            self.hash1 = 0
            self.hash2 = 0
            self.count = 0
            self.suffix_link = None
            self.transitions = dict()

    def build_eertree(s, power1, power2, base1, base2, mod1, mod2):
        root_neg = Node()
        root_neg.length = -1
        root_neg.suffix_link = root_neg
        root_0 = Node()
        root_0.length = 0
        root_0.suffix_link = root_neg
        root_neg.count = 0
        root_0.count = 0

        tree = [root_neg, root_0]
        current_suffix = root_0

        for i in range(len(s)):
            c = s[i]
            current = current_suffix
            while True:
                link_len = current.length
                if link_len == -1:
                    break  # root_neg can always be extended to single character
                start = i - link_len - 1
                if start >= 0 and s[start] == c:
                    break
                current = current.suffix_link

            if c in current.transitions:
                current_suffix = current.transitions[c]
                current_suffix.count += 1
                continue

            # Create new node
            new_node = Node()
            new_node.length = current.length + 2
            if current == root_neg:
                new_node.hash1 = ord(c)
                new_node.hash2 = ord(c)
            else:
                exponent = current.length + 1
                new_hash1 = (ord(c) * power1[exponent] + current.hash1 * base1 + ord(c)) % mod1
                new_hash2 = (ord(c) * power2[exponent] + current.hash2 * base2 + ord(c)) % mod2
                new_node.hash1 = new_hash1
                new_node.hash2 = new_hash2

            # Find suffix link for new_node
            if new_node.length == 1:
                new_node.suffix_link = root_0
            else:
                suffix_candidate = current.suffix_link
                while True:
                    link_len_candidate = suffix_candidate.length
                    if link_len_candidate == -1:
                        suffix_candidate = suffix_candidate.suffix_link
                        break
                    start_candidate = i - link_len_candidate - 1
                    if start_candidate >= 0 and s[start_candidate] == c:
                        break
                    suffix_candidate = suffix_candidate.suffix_link

                if c in suffix_candidate.transitions:
                    new_node.suffix_link = suffix_candidate.transitions[c]
                else:
                    if suffix_candidate == root_neg:
                        new_node.suffix_link = root_0
                    else:
                        new_node.suffix_link = root_0

            current.transitions[c] = new_node
            tree.append(new_node)
            current_suffix = new_node
            current_suffix.count = 1

        # Propagate counts
        for node in reversed(tree[2:]):  # exclude root_neg and root_0
            if node.suffix_link is not None and node.suffix_link.length >= 0:  # valid suffix_link
                node.suffix_link.count += node.count

        return tree

    # Build Eertree for S and T
    s_tree = build_eertree(S, power1, power2, base1, base2, mod1, mod2)
    t_tree = build_eertree(T, power1, power2, base1, base2, mod1, mod2)

    # Create hash map for S's palindromes
    s_palindromes = defaultdict(int)
    for node in s_tree[2:]:  # skip root_neg and root_0
        key = (node.hash1, node.hash2)
        s_palindromes[key] += node.count

    # Calculate the answer
    answer = 0
    for node in t_tree[2:]:  # skip root_neg and root_0
        key = (node.hash1, node.hash2)
        if key in s_palindromes:
            answer += s_palindromes[key] * node.count

    print(answer)

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