后缀数组开始使用scala

Question

今天我尝试使用 scala 创建后缀数组。我能够使用大量代码行来完成它，但后来我听说它可以通过使用压缩和排序仅使用几行代码来创建。

我现在遇到的问题是开头。我尝试使用二进制搜索和 zipWithIndex 来创建以下内容 "tree" 但到目前为止我还无法创建任何内容。我什至不知道仅使用一条线是否可能，但我敢打赌它是哈哈。

我想做的是从一个词"cheesecake"得到一个Seq:

 Seq((cheesecake, 0),
     (heesecake, 1),
     (eesecake, 2),
     (esecake, 3),
     (secake, 4),
     (ecake, 5),
     (cake, 6),
     (ake, 7),
     (ke, 8),
     (e, 9))

有人可以将我推向正确的路径吗？

Answer 1

一种方法，

"cheesecake".reverse.inits.map(_.reverse).zipWithIndex.toArray

Scala 字符串配备了有序集合方法，例如 reverse 和 inits，后者提供了一个字符串集合，其中每个字符串都删除了最新的字符。

Answer 2

生成 String 的所有可能后缀（或任何其他 scala.collection.TraversableLike) you can simply use the tails 方法：

scala> "cheesecake".tails.toList
res25: List[String] = List(cheesecake, heesecake, eesecake, esecake, secake, ecake, cake, ake, ke, e, "")

如果你需要索引，那么你可以使用GenIterable.zipWithIndex：

scala> "cheesecake".tails.toList.zipWithIndex
res0: List[(String, Int)] = List((cheesecake,0), (heesecake,1), (eesecake,2), (esecake,3), (secake,4), (ecake,5), (cake,6), (ake,7), (ke,8), (e,9), ("",10))

Answer 3

您正在寻找 .scan 方法，特别是 .scanRight（因为您想从字符串的末尾（即右侧）开始构建，在下一个字符前添加（看在你的金字塔底部到顶部））。

引用 documentation :

Produces a collection containing cumulative results of applying the operator going right to left.

这里的运算符是：

添加当前字符
递减计数器（因为你的第一个元素是 "cheesecake".length，倒数）

所以 :

scala> s.scanRight (List[(String, Int)]())
                   { case (char, (stringAcc, count)::tl) => (char + stringAcc, count-1)::tl
                     case (c, Nil) => List((c.toString, s.length-1))
                   }
        .dropRight(1)
        .map(_.head)
res12: scala.collection.immutable.IndexedSeq[List[(String, Int)]] =
           Vector((cheesecake,0),
                  (heesecake,1),
                  (eesecake,2),
                  (esecake,3),
                  (secake,4),
                  (ecake,5),
                  (cake,6),
                  (ake,7),
                  (ke,8),
                  (e,9)
                )

末尾的 dropRight(0) 是删除 (List[(String, Int)]()) （第一个参数），它作为开始构建的第一个元素（你可以通过最后一个 e 并迭代 cheesecak，但我发现这样做更容易）。

Answer 4

编辑 - 从我posted (from an Purely Functional Data Structures练习的先前suffix问题，我相信suffixshould/may包括也为空列表，即 "" for String.

scala> def suffix(x: String): List[String] = x.toList match {
     |    case Nil             => Nil
     |    case xxs @ (_ :: xs) => xxs.mkString :: suffix(xs.mkString)
     | }
suffix: (x: String)List[String]

scala> def f(x: String): List[(String, Int)] = suffix(x).zipWithIndex
f: (x: String)List[(String, Int)]

测试

scala> f("cheesecake")
res10: List[(String, Int)] = List((cheesecake,0), (heesecake,1), (eesecake,2), 
            (esecake,3), (secake,4), (ecake,5), (cake,6), (ake,7), (ke,8), (e,9))

后缀数组开始使用scala

Suffix array beginning using scala

string

scala

suffix-array