Suffix automaton
(String/SuffixAutomaton.py)

• View this file on GitHub
• Last update: 2021-06-13 17:43:22+09:00

使い方

SuffixAutomaton()
空文字列 $S$ に対する suffix automaton を構築する。計算量 $O(1)$

• push(char: str)
  文字列 $S$ の末尾に 1 文字 char を追加し、suffix automaton を更新する。計算量 $O(1)$

• has_substring(pattern: str)
  文字列 $S$ にパターン文字列 $P$ (pattern) が部分文字列として存在するかどうか返す。計算量 $O(|P|)$

• number_of_substrings() -> int
  文字列 $S$ の相異なる部分文字列の個数を返す。計算量 $O(|S|)$

Verified with

• TestCase/LibraryChecker/number_of_substrings.suffix_automaton.test.py

Code

class SuffixAutomaton:
    def __init__(self):
        self.last = 0
        self.next = [{}]
        self.link = [-1]
        self.length = [0]

    def _add_node(self, link, length):
        self.next.append({})
        self.link.append(link)
        self.length.append(length)

    def push(self, char):
        nxt, link, length = self.next, self.link, self.length
        new_node = len(nxt)
        self._add_node(-1, length[self.last] + 1)
        p = self.last
        while p != -1 and char not in nxt[p]:
            nxt[p][char] = new_node
            p = link[p]
        q = 0 if p == -1 else nxt[p][char]
        if p == -1 or length[p] + 1 == length[q]:
            link[new_node] = q
        else:
            new_q = len(nxt)
            self._add_node(link[q], length[p] + 1)
            nxt[-1] = {c: nxt[q][c] for c in nxt[q]}
            link[q] = link[new_node] = new_q
            while p != -1 and nxt[p][char] == q:
                nxt[p][char] = new_q
                p = link[p]
        self.last = new_node

    def has_substring(self, pattern):
        p = 0
        for char in pattern:
            if char not in self.next[p]:
                return False
            p = self.next[p][char]
        return True

    def number_of_substrings(self):
        ans = 0
        for i in range(1, len(self.length)):
            ans += self.length[i] - self.length[self.link[i]]
        return ans

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