找到斯卡拉兩個字符串之間的最長公共子串功能的方式

這裏是一個imperative解決方案：找到斯卡拉兩個字符串之間的最長公共子串功能的方式

def longestCommonSubstring(a: String, b: String) : String = { 
    def loop(m: Map[(Int, Int), Int], bestIndices: List[Int], i: Int, j: Int) : String = { 
     if (i > a.length) { 
     b.substring(bestIndices(1) - m((bestIndices(0),bestIndices(1))), bestIndices(1)) 
     } else if (i == 0 || j == 0) { 
     loop(m + ((i,j) -> 0), bestIndices, if(j == b.length) i + 1 else i, if(j == b.length) 0 else j + 1) 
     } else if (a(i-1) == b(j-1) && math.max(m((bestIndices(0),bestIndices(1))), m((i-1,j-1)) + 1) == (m((i-1,j-1)) + 1)) { 
     loop(
      m + ((i,j) -> (m((i-1,j-1)) + 1)), 
      List(i, j), 
      if(j == b.length) i + 1 else i, 
      if(j == b.length) 0 else j + 1 
     ) 
     } else { 
     loop(m + ((i,j) -> 0), bestIndices, if(j == b.length) i + 1 else i, if(j == b.length) 0 else j + 1) 
     } 
    } 
    loop(Map[(Int, Int), Int](), List(0, 0), 0, 0) 
    }

我要尋找一個更緊湊，functional way找到最長公共子串。

來源

2017-06-21 oblivion

def getAllSubstrings(str: String): Set[String] = { 
    str.inits.flatMap(_.tails).toSet 
} 
def longestCommonSubstring(str1: String, str2: String): String = { 
    val str1Substrings = getAllSubstrings(str1) 
    val str2Substrings = getAllSubstrings(str2) 

    str1Substrings.intersect(str2Substrings).maxBy(_.length) 
}

首先獲得一組（以刪除重複項）兩個字符串的所有可能的子串（從here拍攝），然後那些相交集和發現的最長的公用子串。

來源

2017-06-21 09:52:02 thwiegan

的解決方案可能是以下內容：

def substrings(a:String, len:Int): Stream[String] = 
    if(len==0) 
    Stream.empty 
    else 
    a.tails.toStream.takeWhile(_.size>=len).map(_.take(len)) #:: substrings(a, len-1) 

def longestCommonSubstring(a:String, b:String) = 
    substrings(a, a.length).dropWhile(sub => !b.contanis(sub)).headOption

這裏子方法返回料流生產降低原始字符串的長度串，例如「測試」生產「測試」，「TES」，「EST 」，「TE」，「ES」，...

方法longestCommonSubstring需要被包含在字符串從一個產生第一子串b

來源

2017-06-21 10:38:41 Nyavro

我缺少的東西？＃::給我類型不匹配（期望的字符串，實際的流[字符串]）。 ++對我很好用 – thwiegan

而不是dropWhile和headOption，你可以做'substrings（a.a.length）.find（b.contains）' – thwiegan

您擁有的代碼已經正常運行，並不複雜。它還具有比其他當前發佈的解決方案漸近更好的時間效率。

我只是把它簡化，收拾了一下，並修正錯誤：

def longestCommonSubstring(a: String, b: String) = { 
    def loop(bestLengths: Map[(Int, Int), Int], bestIndices: (Int, Int), i: Int, j: Int): String = { 
    if (i > a.length) { 
     val bestJ = bestIndices._2 
     b.substring(bestJ - bestLengths(bestIndices), bestJ) 
    } else { 
     val currentLength = if (a(i-1) == b(j-1)) bestLengths(i-1, j-1) + 1 else 0 
     loop(
     bestLengths + ((i, j) -> currentLength), 
     if (currentLength > bestLengths(bestIndices)) (i, j) else bestIndices, 
     if (j == b.length) i + 1 else i, 
     if (j == b.length) 1 else j + 1) 
    } 
    } 

    loop(Map.empty[(Int, Int), Int].withDefaultValue(0), (0, 0), 1, 1) 
}

來源

2017-06-21 12:17:47 Kolmar

只是想扔進去，他要求一個緊湊的（我明白作爲可讀）解決方案。雖然您的解決方案可能會有更好的效率，但對某些人來說，調試此代碼可能會更困難。儘管如此，提及它當然很重要。 – thwiegan

@thwiegan我其實同意你的看法。我發佈這個答案的一個原因是爲了解決原始代碼不起作用的錯誤觀念：它沒有可變性，它只是一個尾遞歸函數。 – Kolmar

@thwiegan另外我認爲一般來說，對於算法代碼，在你已經編寫了更高效的版本和單元測試之後，除了可能增加新的功能之外，幾乎不需要將來的維護。但這個問題通常花時間來編寫和測試它，以及它是否會在您的數據大小上實際運行得更快......所以我認爲您的觀點是正確的，但我想指出這種替代方法。 – Kolmar

我認爲有爲理解代碼看起來非常清晰和功能。

def getSubstrings(s:String) = 
    for { 
    start <- 0 until s.size 
    end <- start to s.size 

    } yield s.substring(start, end) 

def getLongest(one: String, two: String): Seq[String] = 

    getSubstrings(one).intersect(getSubstrings(two)) 
.groupBy(_.length).maxBy(_._1)._2

最後函數返回一個序列[字符串]至於結果可能包含幾個子具有相同的最大長度

來源

2017-06-21 22:24:40

找到斯卡拉兩個字符串之間的最長公共子串功能的方式

回答

相關問題