使用Scala开始后缀数组

Question

今天我正在尝试使用Scala创建后缀数组。我已经用大量的代码完成了它，但是后来听说可以使用zip和sorting仅使用几行代码完成。

我目前遇到的问题是开始部分。我尝试使用二进制搜索和zipWithIndex创建以下“树状结构”，但到目前为止我还没有成功创建任何东西。我甚至不知道是否可能只使用一行代码完成，但我敢打赌这是可能的。

我想做的是从单词“cheesecake”中获取一个Seq：

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

请问有人能指导我走向正确的道路吗？

- Duzzz

---

非常感谢你们所有人的帮助。我的代码现在看起来好多了 :) 下次我再卡住时，再见！ - Duzzz

你可能会对这个Haskell实现感兴趣 - http://codereview.stackexchange.com/questions/66952/create-suffixes-function-on-list - Kevin Meredith

Answer 1

要生成一个字符串（或任何其他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))

- mutantacule

Answer 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上迭代，但我发现这种方法更容易）。

- Marth

---

好的，是的，我看到了答案（并点赞了它，因为对于这个问题来说比我的解释更清晰）。但是，在问题中看到“金字塔”让我想到了 .scan，这是一个通用的解决此类问题的方法（折叠和累积中间结果）（在这里并不需要）。 - Marth

抱歉我把那个回答发错了。也就是说，我把你的 dropRight 推荐复制到了 Kossi 的回答下面，但实际上我想把它放在别处。干得好 :> - Drew

Answer 3

编辑 - 我之前发布的一个关于suffix的问题（来自纯函数数据结构练习），我认为suffix也可以包括空列表，即对于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))

- Kevin Meredith

Answer 4

一种方法，

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

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

- elm