SA-IS法
素朴に実装すると$ O(N^2\log N)の接尾辞配列を$ O(N)で作る方法
接尾辞配列とは
code:python
data = "abracadabra$"
buf = []
for i in range(len(data)):
buf.append((datai:, i))
buf.sort()
for x in buf:
print(x)
接尾辞配列ができると特定のキーワードの出現場所を二分探索で効率よく発見できる
先頭文字に対するバケットソートを使う
難しい
噛み砕いた解説
http://shogo82148.github.io/homepage/memo/algorithm/suffix-array/
わかりやすい?解説
https://mametter.hatenablog.com/entry/20180130/p1