scalaのsuffixArray

とりあえず作ったが、問題点が幾つかある。

class SuffixArray(str:String) { 
  val sortedArray = this.parse(str)

  import scala.collection.mutable.HashMap
  def parse(str:String) : Array[HashMap[String, Any]] = {
    var strArray = new Array[HashMap[String, Any]](str.length)
    for (i <- 0 until str.length) {
      strArray(i) = HashMap("index" -> i, "value" -> str.drop(i))
    }   
    val sortedArray = strArray.sortWith((a, b) => a("value").toString < b("value").toString)
    return sortedArray
  }

  def search(str:String) : Int = {
    val idx = this.search_index(str)
    val res = if (idx < 0) -1 else this.sortedArray(idx)("index").asInstanceOf[Int]
    return res
  }

  def search_index(str:String) : Int = {
    var upper = this.sortedArray.length - 1
    var lower = 0
    while (upper >= lower) {
      var i = lower + (upper - lower) / 2
      var s = this.sortedArray(i)("value").toString
      if (s.startsWith(str)) return i
      if (s < str) lower = i + 1 else upper = i - 1
    }
    return -1
  }
}

こんな風に使う

object SuffixArrayTest {
  def main(args: Array[String]) {
    val sa = new SuffixArray("abracadabra")
    println(sa.search("cadab").toString) // 4
  } 
}