接尾辞配列 ($\mathrm{O}(N (\log^2 N))$)
(String/SA_nlogn2.py)

• View this file on GitHub
• Last update: 2021-01-16 10:09:20+09:00

Verified with

• TestCase/LibraryChecker/suffixarray.nlogn2.test.py

Code

class SuffixArray:
    def __init__(self, string):
        self.n = len(string)
        self.sa = [i for i in range(self.n + 1)]
        self.lcp = [0] * (self.n + 1)
        if type(string[0]) == str:
            array = [ord(char) for char in string]
        else:
            array = string
        self.build_SA(array)
        self.build_LCP(array)

    def build_SA(self, array):
        rank = [-1] * (2 * self.n + 1)
        rank[0:self.n] = array

        tmp = [0] * (self.n + 1)
        cmp_sa = lambda i: (rank[i] << 32) | (rank[i + k] + 1)

        k = 1
        while k <= self.n:
            self.sa.sort(key=cmp_sa)
            val = self.sa[0]
            tmp[val] = 0
            for nxt_val in self.sa[1:]:
                tmp[nxt_val] = tmp[val] + (cmp_sa(val) < cmp_sa(nxt_val))
                val = nxt_val
            rank[0:self.n + 1] = tmp
            k <<= 1

    def build_LCP(self, array):
        rank = [0] * (self.n + 1)
        for i, val in enumerate(self.sa):
            rank[val] = i
        h = 0
        for i, rk in enumerate(rank):
            j = self.sa[rk - 1]
            if h > 0:
                h -= 1
            while j + h < self.n and i + h < self.n:
                if array[j + h] != array[i + h]:
                    break
                else:
                    h += 1
            self.lcp[rk - 1] = h

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