使用scala开始的后缀数组

Question

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

我现在遇到的问题是从一开始.我尝试使用二进制搜索和zipWithIndex创建以下"树",但到目前为止我还没有能够创建任何东西.我甚至不知道是否有可能只使用一条线,但我打赌它是大声笑.

我想做的是从一个词"芝士蛋糕"得到一个Seq:

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

有人会把我推到正确的道路上吗？

Answer 1

要生成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))