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