satashun https://blog.hatena.ne.jp/satashun/ gdgdiary https://satashun.hatenablog.com/ Suffix Arrayを空間・時間計算量共に線形で構築出来るというアルゴリズムSA-ISを, 以前ふわっと読んだことはあったけれど真面目に読みなおしました. よく出来過ぎだと思う. 細かいところの理解が間違っていたら教えて下さい. ざっくりとした流れしか書きません. ちゃんとした証明とかは元論文を見てください. というかこんな記事よりiwiさんのブログとかがわかりやすいと思うけど自分で忘れないために書きました. (元論文: Linear Suffix Array Construction by Almost Pure Induced-Sorting)文字列の最後には最小の番兵を置いておく.記… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsatashun.hatenablog.com%2Fentry%2F2016%2F09%2F11%2F162459" title="SA-IS - gdgdiary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-09-11 16:24:59 rich https://satashun.hatenablog.com/entry/2016/09/11/162459 1.0 100%