読者です 読者をやめる 読者になる 読者になる

人権真骨頂

とくがたかいことでゆうめい

SuffixArrayをCrystalで実装してみた

blog.shibayu36.org

この記事を見てCrystalでもやってみたくなったのでやってみた.

class SuffixArray
  def self.make(str : String) : Array(Int32)
    (0...str.size).map { |i| {str[i...str.size], i} }.sort_by { |p| p.first }.map(&.last)
  end
end

こんな感じになった.

require "spec"

describe SuffixArray do
  it "returns empty array" do
    SuffixArray.make("").should eq [] of Int32
  end

  it "returns suffix array" do
    SuffixArray.make("banana").should eq [5, 3, 1, 0, 4, 2]
  end
end

一応テストも書いてみた.

まとめ

文字列アルゴリズムの学びかた - Hatena Developer Blog

SuffixArray聞いたことはあったけど,どういうものかは知らなかったのでなるほど...という感じだった.自分もアルゴリズムの勉強をやっていきたいので,なんかRubyで学ぶアルゴリズム的なのがあればCrystalでも簡単に実装できそうで良さそう.