結果

問題 No.263 Common Palindromes Extra
ユーザー neterukunneterukun
提出日時 2021-10-04 23:30:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,180 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 86,976 KB
実行使用メモリ 597,920 KB
最終ジャッジ日時 2023-09-30 06:21:08
合計ジャッジ時間 8,068 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
81,676 KB
testcase_01 AC 69 ms
71,188 KB
testcase_02 AC 84 ms
75,820 KB
testcase_03 AC 205 ms
89,548 KB
testcase_04 AC 432 ms
156,956 KB
testcase_05 AC 420 ms
169,104 KB
testcase_06 AC 146 ms
84,184 KB
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 AC 319 ms
167,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Node:
    def __init__(self, length, count):
        self.length = length
        self.count = count
        self.suffix_link = 0
        self.link = {}


class Eertree:
    def __init__(self):
        self.nodes = []
        self.string = []

        self.root_odd = Node(-1, 0)
        self.nodes.append(self.root_odd)

        self.root_even = Node(0, 0)
        self.nodes.append(self.root_even)

        self.cur = 0

    def prev_palindrome_node(self, idx):
        size = len(self.string) - 1
        while True:
            i = size - 1 - self.nodes[idx].length
            if i >= 0 and self.string[i] == self.string[-1]:
                break
            idx = self.nodes[idx].suffix_link
        return idx

    def add(self, char):
        self.string.append(char)
        idx = self.prev_palindrome_node(self.cur)

        if char in self.nodes[idx].link:
            self.cur = self.nodes[idx].link[char]
            self.nodes[self.cur].count += 1
            return

        self.nodes[idx].link[char] = len(self.nodes)
        new = Node(self.nodes[idx].length + 2, 1)
        self.nodes.append(new)
        self.cur = self.nodes[idx].link[char]

        if new.length == 1:
            new.suffix_link = 1
        else:
            idx = self.prev_palindrome_node(self.nodes[idx].suffix_link)
            new.suffix_link = self.nodes[idx].link[char]

    def frequency_build(self):
        n = len(self.nodes)
        freq = [0] * n
        for i in reversed(range(n)):
            freq[i] += self.nodes[i].count
            freq[self.nodes[i].suffix_link] += freq[i]
        return freq


s = input()
t = input()

et_s = Eertree()
for char in s:
    et_s.add(char)

et_t = Eertree()
for char in t:
    et_t.add(char)

freq_s = et_s.frequency_build()
freq_t = et_t.frequency_build()

ans = 0
stack = [(0, 0), (1, 1)]
while stack:
    idx_s, idx_t = stack.pop()
    if idx_s > 1:
        ans += freq_s[idx_s] * freq_t[idx_t]
    for char in et_s.nodes[idx_s].link:
        if char in et_t.nodes[idx_t].link:
            nxt_s = et_s.nodes[idx_s].link[char]
            nxt_t = et_t.nodes[idx_t].link[char]
            stack.append((nxt_s, nxt_t))
print(ans)
0