回分木 (Palindrome tree)
(String/PalindromicTree.py)

• View this file on GitHub
• Last update: 2021-10-04 23:59:22+09:00
• Link: https://math314.hateblo.jp/entry/2016/12/19/005919

Verified with

• TestCase/yukicoder/yuki0263.test.py

Code

# PalindromicTree
# https://math314.hateblo.jp/entry/2016/12/19/005919

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


class PalindromicTree:
    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)
        frequency = [0] * n
        for i in reversed(range(n)):
            frequency[i] += self.nodes[i].count
            frequency[self.nodes[i].suffix_link] += frequency[i]
        return frequency

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page