5

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

我现在遇到的问题是一开始。我尝试使用二进制搜索和 zipWithIndex 来创建以下“树”，但到目前为止我还无法创建任何东西。我什至不知道仅使用一条线是否有可能，但我敢打赌它是大声笑。

我想做的是从“芝士蛋糕”这个词中得到一个Seq：

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

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

4

4 回答 4

7

要生成 a String（或任何其他scala.collection.TraversableLike）的所有可能后缀，您可以简单地使用以下 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))
于 2015-05-06T11:25:02.503 回答
2

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

引用文档：

生成一个集合，其中包含应用从右到左的运算符的累积结果。

这里的操作员是：

  • 前置当前字符
  • 递减计数器（因为你的第一个元素是"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，但我发现这样做更容易）。

于 2015-05-06T11:32:51.090 回答
1

一种方法，

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

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

于 2015-05-06T11:23:55.180 回答
1

编辑- 从我发布suffix的上一个问题（来自纯功能数据结构练习，我相信应该/可能也包括空列表，即对于String。suffix""

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))
于 2015-05-07T15:32:05.497 回答