找到斯卡拉两个字符串之间的最长公共子串功能的方式

问题描述：

这里是一个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找到最长公共子串。

答

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拍摄），然后那些相交集和发现的最长的公用子串。

答

的解决方案可能是以下内容：

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

我缺少的东西？＃::给我类型不匹配（期望的字符串，实际的流[字符串]）。 ++对我很好用 – 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) 
}

只是想扔进去，他要求一个紧凑的（我明白作为可读）解决方案。虽然您的解决方案可能会有更好的效率，但对某些人来说，调试此代码可能会更困难。尽管如此，提及它当然很重要。 – 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

最后函数返回一个序列[字符串]至于结果可能包含几个子具有相同的最大长度

找到斯卡拉两个字符串之间的最长公共子串功能的方式

相关推荐