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でも簡単に実装できそうで良さそう．