Suffix Array
文字列$ SのSuffix Arrayとは、文字列$ Sの接尾辞であって、長さが$ 1から$ |S|までのものすべてを辞書順に並べたもの。
文字列のリストを陽に持つわけではなく、Suffixの開始位置のインデントのリストで持つ。
これがSA-ISというアルゴリズムを使って$ O(N)で構築できる。 $ Tについて
$ Tが$ S中に何回出現するか
$ Tが$ S中に出現する位置の列挙
などがSAを二分探索することで$ O(|T|\mathrm{log}|S|)で求められる。
code: bs_in_sa.py
from atcoder import string
def is_ok(arg, T):
if arg == 0: True
if arg > len(S): False
arg -= 1
return S[saarg : saarg + len(T)] < T def bs(ok, ng, T):
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, T):
ok = mid
else:
ng = mid
return ok
def bs_interval(ok, ng, T):
"""
ok = 0, ng = |S| + 1
SA内で、prefixがTと一致する半開区間 [L, R)を返す
"""
T2 = list(T)
T2-1 = chr(ord(T2-1) + 1) L = bs(ok, ng, T)
R = bs(ok, ng, "".join(T2))
return L, R
S = input()
sa = string.suffix_array(S)