結果

問題 No.2606 Mirror Relay
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:57:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 326 ms / 2,000 ms
コード長 2,557 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 83,028 KB
実行使用メモリ 218,856 KB
最終ジャッジ日時 2025-03-20 18:58:44
合計ジャッジ時間 8,233 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class Eertree:
    def __init__(self):
        self.nodes = []
        self.root_neg1 = EertreeNode(-1, None)
        self.root_0 = EertreeNode(0, self.root_neg1)
        self.root_neg1.suffix_link = self.root_neg1
        self.root_0.suffix_link = self.root_neg1
        self.last = self.root_0
        self.max_pal = 0

    def add_char(self, c, index):
        current = self.last
        while True:
            edge = index - 1 - current.length
            if edge >= 0 and c == self.s[edge]:
                break
            current = current.suffix_link
        if c in current.transitions:
            self.last = current.transitions[c]
            self.last.count += 1
            return
        new_node = EertreeNode(current.length + 2, self.root_0)
        self.nodes.append(new_node)
        current.transitions[c] = new_node
        if new_node.length == 1:
            new_node.suffix_link = self.root_0
        else:
            suffix_current = current.suffix_link
            while True:
                edge = index - 1 - suffix_current.length
                if edge >= 0 and c == self.s[edge]:
                    break
                suffix_current = suffix_current.suffix_link
            new_node.suffix_link = suffix_current.transitions.get(c, self.root_0)
        self.last = new_node
        new_node.count = 1

    def build(self, s):
        self.s = s
        for idx, c in enumerate(s):
            self.add_char(c, idx)
            if self.last.length > self.max_pal:
                self.max_pal = self.last.length

    def compute_counts(self):
        nodes_sorted = sorted(self.nodes, key=lambda x: -x.length)
        for node in nodes_sorted:
            if node.suffix_link is not None and node.suffix_link.length >= 0:
                node.suffix_link.count += node.count

def main():
    S = input().strip()
    eertree = Eertree()
    eertree.build(S)
    eertree.compute_counts()

    s_values = {}
    max_score = 0
    for node in eertree.nodes:
        s = node.length * node.count
        parent = node.suffix_link
        if parent.length >= 0:
            s += s_values.get(parent, 0)
        s_values[node] = s
        if s > max_score:
            max_score = s
    root_0_s = eertree.root_0.count * 0
    if root_0_s > max_score:
        max_score = root_0_s
    print(max_score)

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