結果

問題 No.263 Common Palindromes Extra
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:47:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,646 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 452,432 KB
最終ジャッジ日時 2025-06-12 20:48:19
合計ジャッジ時間 9,026 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 7 TLE * 1 MLE * 2 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD1 = 10**18 + 3
MOD2 = 10**18 + 7
BASE = 911382629

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

    def compute_hash(s):
        n = len(s)
        pow_base = [1] * (n + 1)
        for i in range(1, n+1):
            pow_base[i] = (pow_base[i-1] * BASE) % MOD1
        h1 = [0] * (n+1)
        for i in range(n):
            h1[i+1] = (h1[i] * BASE + ord(s[i])) % MOD1
        h2 = [0] * (n+1)
        for i in range(n):
            h2[i+1] = (h2[i] * BASE + ord(s[i])) % MOD2
        return h1, h2, pow_base

    h1_S, h2_S, pow_S = compute_hash(S)
    h1_T, h2_T, pow_T = compute_hash(T)

    class Node:
        __slots__ = ['len', 'suff_link', 'trans', 'count', 'h1', 'h2']
        def __init__(self):
            self.len = 0
            self.suff_link = None
            self.trans = {}
            self.count = 0
            self.h1 = 0
            self.h2 = 0

    def build_palindrom_tree(s, n, h1, h2, pow_base):
        root_neg = Node()
        root_neg.len = -1
        root_neg.suff_link = root_neg
        root_zero = Node()
        root_zero.len = 0
        root_zero.suff_link = root_neg
        tree = [root_neg, root_zero]
        last = root_zero
        for i in range(n):
            c = s[i]
            current = last
            while True:
                l = current.len
                if i - l - 1 >= 0 and s[i - l - 1] == c:
                    break
                current = current.suff_link
            if c in current.trans:
                last = current.trans[c]
                last.count += 1
                continue
            new_node = Node()
            new_node.len = current.len + 2
            tree.append(new_node)
            current.trans[c] = new_node
            last = new_node
            if new_node.len == 1:
                new_node.suff_link = root_zero
            else:
                suff = current.suff_link
                while True:
                    l = suff.len
                    if i - l - 1 >= 0 and s[i - l - 1] == c:
                        break
                    suff = suff.suff_link
                new_node.suff_link = suff.trans.get(c, root_zero)
            new_node.count = 1
            l = new_node.len
            start = i - l + 1
            end = i + 1
            new_node.h1 = (h1[end] - h1[start] * pow_base[end - start]) % MOD1
            new_node.h2 = (h2[end] - h2[start] * pow_base[end - start]) % MOD2
        return tree

    tree_S = build_palindrom_tree(S, len(S), h1_S, h2_S, pow_S)
    tree_T = build_palindrom_tree(T, len(T), h1_T, h2_T, pow_T)

    count_S = defaultdict(int)
    for node in tree_S[1:]:
        if node.len >= 0:
            count_S[(node.h1, node.h2)] += node.count

    for node in tree_S[1:]:
        if node.len >= 0:
            current = node.suff_link
            while current != tree_S[0] and current != tree_S[1]:
                count_S[(current.h1, current.h2)] += node.count
                current = current.suff_link

    count_T = defaultdict(int)
    for node in tree_T[1:]:
        if node.len >= 0:
            count_T[(node.h2, node.h1)] += node.count

    for node in tree_T[1:]:
        if node.len >= 0:
            current = node.suff_link
            while current != tree_T[0] and current != tree_T[1]:
                count_T[(current.h2, current.h1)] += node.count
                current = current.suff_link

    result = 0
    for (h1, h2), cnt_S in count_S.items():
        cnt_T = count_T.get((h2, h1), 0)
        result += cnt_S * cnt_T

    print(result)

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