後綴數組開始使用scala

今天我試圖用scala創建後綴數組。我能夠用大量的代碼完成它，但後來我聽說它可以通過使用壓縮和排序只使用幾行來創建。後綴數組開始使用scala

我現在的問題是與開始。我嘗試使用二進制搜索和zipWithIndex來創建以下「樹」，但到目前爲止我還沒有能夠創建任何東西。我甚至不知道只用一條線是否可能，但我敢打賭它是大聲笑。

我想要做的就是從一個字「芝士蛋糕」中獲得一個序列：

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

可能有人輕推我到正確的道路？

來源

2015-05-06 Duzzz

非常感謝你們所有的人。我的代碼現在看起來好多了:)直到下一次我卡住了 – Duzzz

你可能會發現Haskell的實現很有趣 - http://codereview.stackexchange.com/questions/66952/create-suffixes-function-on-list –

要生成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-06 11:25:02 kosii

可能是val s2 =「芝士蛋糕」.tails.toList .......然後s2.dropRight（1） – Drew

一種方法，

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

斯卡拉串都配備了有序集合方法，如reverse和inits，後者提供的字符串的集合，每個字符串已跌至最新的字符。

來源

2015-05-06 11:23:55 elm

您正在查找.scan方法，特別是.scanRight（因爲您要從字符串的末尾（即右側）開始構建，需要添加下一個字符r（看你的金字塔底部到頂部））。

引述documentation：

生成包含應用操作會從右到左的累積結果的集合。

在這裏，運營商是：

前面加上當前字符
遞減計數器（因爲你的第一個元素是"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-06 11:32:51 Marth

嗯，我看到了答案（並提高了答案，因爲這個問題比我更清晰）。但在問題中看到'金字塔'讓我想到'.scan'，這是這類問題的一般解決方案（摺疊和積累中間結果）（這裏不需要）。 – Marth

對不起，我發佈了錯誤的答案。那是我偷了你的dropRight的建議，並把它放在Kossi的下面，我打算放它。好工作：> – Drew

編輯 - 從以前suffix問題，我posted（從Purely Functional Data Structures鍛鍊，我相信suffix應該/可能包括空單過，即"" for 字符串。

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-07 15:32:05

後綴數組開始使用scala

回答

相關問題