Source code for titan_pylib.string.get_suffix_array

 1from titan_pylib.string.hash_string import HashString
 2from titan_pylib.algorithm.sort.merge_sort import merge_sort
 3
 4

[docs]
 5def get_suffix_array(s: str, hs: HashString) -> list[int]:
 6    """suffix_arrayを求めます。
 7
 8    ロリハで大小比較をするため、比較関数に :math:`O(logn)` 、
 9    ソートが :math:`O(nlogn*(比較関数の計算量))` で、
10    全体 :math:`O(nlog^2n)` です。
11
12    Args:
13        s (str): 文字列です。
14        hs (HashString): ``HashString`` です。
15
16    Returns:
17        list[int]: suffix_array です。
18    """
19
20    def cmp(u: int, v: int) -> bool:
21        ok, ng = 0, min(n - u, n - v)
22        while ng - ok > 1:
23            mid = (ok + ng) >> 1
24            if hs.get(u, u + mid) == hs.get(v, v + mid):
25                ok = mid
26            else:
27                ng = mid
28        return s[u + ok] < s[v + ok]
29
30    n = len(s)
31    return merge_sort(range(n), key=cmp)