scala中查找两个字符串之间最长公共子串的函数方法

oiopk7p5  于 2022-12-23  发布在  Scala
关注(0)|答案(7)|浏览(156)

下面是一个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找到最长的公共子字符串。

scala

7条答案

按热度按时间
de90aj5v

de90aj5v1#

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）（以删除重复项），然后求这些集合的交集，找到公共子字符串中最长的一个。

赞(0）分享  回复(0）举报  2022-12-23
zbwhf8kr

zbwhf8kr2#

你的代码已经很实用了，也不是那么复杂。它也比目前发布的其他解决方案具有更好的时间效率。
我只想简化一下，清理一下，修复一下bug：

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(
        if (currentLength != 0) bestLengths + ((i, j) -> currentLength) else bestLengths, 
        if (currentLength > bestLengths(bestIndices)) (i, j) else bestIndices, 
        if (j == b.length) i + 1 else i,
        if (j == b.length) 1 else j + 1)
    }
  }

  if (b.isEmpty) ""
  else loop(Map.empty[(Int, Int), Int].withDefaultValue(0), (0, 0), 1, 1)
}
赞(0）分享  回复(0）举报  2022-12-23
luaexgnf

luaexgnf3#

**旁注：**这是我对这个问题的第三个答案，因为StackOverflow策略不允许从根本上替换以前答案的内容。感谢@Kolmar的反馈，这个新答案比my prior answer性能更好。

LCS（最长公共子串）问题空间已经投入了许多时间来寻找最优解决方案策略。要观察更一般的计算机科学问题和最优策略，请查看this Wikipedia article。这篇Wikipedia文章的后面是一些描述实现策略的伪代码。
基于Wikipedia文章的伪代码，我将给出几种不同的解决方案，目的是允许用户复制/粘贴所需的特定解决方案，而无需进行大量的重构：

  1. LCSubstr：将使用 * 命令式可变样式 * 的Wikipedia文章伪代码翻译成Scala
  2. LCSubstrFp：将LCSubstr重构为惯用的 *Scala函数不可变样式 *
  3. longestCommonSubstrings：重构LCSubstrFp以使用描述性名称（例如left和right，而不是s和t），并跳过在Map中存储零长度
  4. longestCommonSubstringsFast：重构longestCommonSubstrings以深度优化CPU和内存
  5. longestCommonSubstringsWithIndexes：重构longestCommonSubstringsFast以增强返回值，方法是将每个条目扩展为(String, (Int, Int))的元组，其中包括找到的子字符串和每个输入String中找到子字符串的索引（**注意：**如果同一String出现多次，则会创建索引对的组合扩展）
  6. firstLongestCommonSubstring：longestCommonSubstringsFast的一个注重效率的版本，当只关心第一个LCS而想忽略相同大小的其他LCS时，它提供了提前终止的机会。
    1.***奖励：***x1月19日1x：重构longestCommonSubstringsFast以增加内部实现的可变性，同时在外部保留函数的引用透明性。
    对于OP的请求，更直接的答案应该在LCSubstrFp和longestCommonSubstringsFast之间。LCSubstrFp是最直接的，但效率相当低。使用longestCommonSubstringsFast效率更高，因为它最终使用的CPU和GC要少得多。如果函数实现中包含和约束的内部互操作性是可以接受的，那么longestCommonSubstringsUltimate是迄今为止CPU负担和内存占用最小的版本。

LC子序列

翻译成Scala的维基百科文章伪代码，其中使用了 * 命令式可变样式 *。
这样做的目的是尽可能地用Scala来重现一对一的实现。例如，Scala假设String使用从零开始的索引，而伪代码显然使用从一开始的索引，这需要一些调整。

def LCSubstr(s: String, t: String): scala.collection.mutable.Set[String] =
  if (s.nonEmpty && t.nonEmpty) {
    val l: scala.collection.mutable.Map[(Int, Int), Int] = scala.collection.mutable.Map.empty
    var z: Int = 0
    var ret: scala.collection.mutable.Set[String] = scala.collection.mutable.Set.empty

    (0 until s.length).foreach {
      i =>
        (0 until t.length).foreach {
          j =>
            if (s(i) == t(j)) {
              if ((i == 0) || (j == 0))
                l += ((i, j) -> 1)
              else
                l += ((i, j) -> (l((i - 1, j - 1)) + 1))
              if (l((i, j)) > z) {
                z = l((i, j))
                ret = scala.collection.mutable.Set(s.substring(i - z + 1, i + 1))
              }
              else
                if (l((i, j)) == z)
                  ret += s.substring(i - z + 1, i + 1)
            } else
              l += ((i, j) -> 0)
        }
    }

    ret
  }
  else scala.collection.mutable.Set.empty

LC减影Fp

将LCSubstr重构为惯用的 *Scala函数不可变样式 *。
所有的命令式和变异代码都被函数和不可变代码所取代，两个for循环被递归所取代。

def LCSubstrFp(s: String, t: String): Set[String] =
  if (s.nonEmpty && t.nonEmpty) {
    @scala.annotation.tailrec
    def recursive(
      i: Int = 0,
      j: Int = 0,
      z: Int = 0,
      l: Map[(Int, Int), Int] = Map.empty,
      ret: Set[String] = Set.empty
    ): Set[String] =
      if (i < s.length) {
        val (newI, newJ) =
          if (j < t.length - 1) (i, j + 1)
          else (i + 1, 0)
        val lij =
          if (s(i) != t(j)) 0
          else
            if ((i == 0) || (j == 0)) 1
            else l((i - 1, j - 1)) + 1
        recursive(
          newI,
          newJ,
          if (lij > z) lij
          else z,
          l + ((i, j) -> lij),
          if (lij > z) Set(s.substring(i - lij + 1, i + 1))
          else
            if ((lij == z) && (z > 0)) ret + s.substring(i - lij + 1, i + 1)
            else ret
        )
      }
      else ret

    recursive()
  }
  else Set.empty

最长公用子字符串

重构LCSubstrFp以使用描述性名称（例如left和right，而不是s和t），并跳过在Map中存储零长度。
除了增强可读性之外，这种重构还省去了在lengthByIndexLongerAndIndexShorter中存储零长度值的步骤，从而大大减少了“内存扰动”的数量。同样，在函数式风格的调整中，通过将Set Package 在Option中，返回值也得到了增强，不再返回空的Set。如果返回值是Some，所包含的X1 M39 N1 X将总是包含至少一个项目。

def longestCommonSubstrings(left: String, right: String): Option[Set[String]] =
  if (left.nonEmpty && right.nonEmpty) {
    val (shorter, longer) =
      if (left.length < right.length) (left, right)
      else (right, left)

    @scala.annotation.tailrec
    def recursive(
      indexLonger: Int = 0,
      indexShorter: Int = 0,
      currentLongestLength: Int = 0,
      lengthByIndexLongerAndIndexShorter: Map[(Int, Int), Int] = Map.empty,
      accumulator: List[Int] = Nil
    ): (Int, List[Int]) =
      if (indexLonger < longer.length) {
        val length =
          if (longer(indexLonger) != shorter(indexShorter)) 0
          else
            if ((indexShorter == 0) || (indexLonger == 0)) 1
            else lengthByIndexLongerAndIndexShorter.getOrElse((indexLonger - 1, indexShorter - 1), 0) + 1
        val newCurrentLongestLength =
          if (length > currentLongestLength) length
          else currentLongestLength
        val newLengthByIndexLongerAndIndexShorter =
          if (length > 0) lengthByIndexLongerAndIndexShorter + ((indexLonger, indexShorter) -> length)
          else lengthByIndexLongerAndIndexShorter
        val newAccumulator =
          if ((length < currentLongestLength) || (length == 0)) accumulator
          else {
            val entry = indexShorter - length + 1
            if (length > currentLongestLength) List(entry)
            else entry :: accumulator
          }
        if (indexShorter < shorter.length - 1)
          recursive(
            indexLonger,
            indexShorter + 1,
            newCurrentLongestLength,
            newLengthByIndexLongerAndIndexShorter,
            newAccumulator
          )
        else
          recursive(
            indexLonger + 1,
            0,
            newCurrentLongestLength,
            newLengthByIndexLongerAndIndexShorter,
            newAccumulator
          )
      }
      else (currentLongestLength, accumulator)

    val (length, indexShorters) = recursive()
    if (indexShorters.nonEmpty)
      Some(
        indexShorters
          .map {
            indexShorter =>
              shorter.substring(indexShorter, indexShorter + length)
          }
          .toSet
      )
    else None
  }
  else None

最长常用子字符串快速

重构longestCommonSubstrings以深度优化CPU和内存。
在保持功能性和不可变性的同时，消除了每一点低效，执行速度比longestCommonSubstrings提高了数倍。大部分成本降低是通过将整个矩阵的Map替换为仅跟踪当前行和先前行的一对List来实现的。
要轻松查看与longestCommonSubstrings、please view this visual diff的区别。

def longestCommonSubstringsFast(left: String, right: String): Option[Set[String]] =
  if (left.nonEmpty && right.nonEmpty) {
    val (shorter, longer) =
      if (left.length < right.length) (left, right)
      else (right, left)

    @scala.annotation.tailrec
    def recursive(
      indexLonger: Int = 0,
      indexShorter: Int = 0,
      currentLongestLength: Int = 0,
      lengthsPrior: List[Int] = List.fill(shorter.length)(0),
      lengths: List[Int] = Nil,
      accumulator: List[Int] = Nil
    ): (Int, List[Int]) =
      if (indexLonger < longer.length) {
        val length =
          if (longer(indexLonger) != shorter(indexShorter)) 0
          else lengthsPrior.head + 1
        val newCurrentLongestLength =
          if (length > currentLongestLength) length
          else currentLongestLength
        val newAccumulator =
          if ((length < currentLongestLength) || (length == 0)) accumulator
          else {
            val entry = indexShorter - length + 1
            if (length > currentLongestLength) List(entry)
            else entry :: accumulator
          }
        if (indexShorter < shorter.length - 1)
          recursive(
            indexLonger,
            indexShorter + 1,
            newCurrentLongestLength,
            lengthsPrior.tail,
            length :: lengths,
            newAccumulator
          )
        else
          recursive(
            indexLonger + 1,
            0,
            newCurrentLongestLength,
            0 :: lengths.reverse,
            Nil,
            newAccumulator
          )
      }
      else (currentLongestLength, accumulator)

    val (length, indexShorters) = recursive()
    if (indexShorters.nonEmpty)
      Some(
        indexShorters
          .map {
            indexShorter =>
              shorter.substring(indexShorter, indexShorter + length)
          }
          .toSet
      )
    else None
  }
  else None

最长的带索引的公共子字符串

重构longestCommonSubstringsFast以增强返回值，方法是将每个条目扩展为(String, (Int, Int))的元组，其中包括找到的子字符串和每个输入String中找到子字符串的索引。

**注意：**如果同一个String出现多次，则会创建索引对的组合展开。

在函数式风格的调整中，返回值也得到了增强，通过将List Package 在Option中，不再返回空的List。如果返回的值是Some，则包含的List将始终包含至少一个项。

def longestCommonSubstringsWithIndexes(left: String, right: String): Option[List[(String, (Int, Int))]] =
  if (left.nonEmpty && right.nonEmpty) {
    val isLeftShorter = left.length < right.length
    val (shorter, longer) =
      if (isLeftShorter) (left, right)
      else (right, left)

    @scala.annotation.tailrec
    def recursive(
      indexLonger: Int = 0,
      indexShorter: Int = 0,
      currentLongestLength: Int = 0,
      lengthsPrior: List[Int] = List.fill(shorter.length)(0),
      lengths: List[Int] = Nil,
      accumulator: List[(Int, Int)] = Nil
    ): (Int, List[(Int, Int)]) =
      if (indexLonger < longer.length) {
        val length =
          if (longer(indexLonger) != shorter(indexShorter)) 0
          else lengthsPrior.head + 1
        val newCurrentLongestLength =
          if (length > currentLongestLength) length
          else currentLongestLength
        val newAccumulator =
          if ((length < currentLongestLength) || (length == 0)) accumulator
          else {
            val entry = (indexLonger - length + 1, indexShorter - length + 1)
            if (length > currentLongestLength) List(entry)
            else entry :: accumulator
          }
        if (indexShorter < shorter.length - 1)
          recursive(
            indexLonger,
            indexShorter + 1,
            newCurrentLongestLength,
            lengthsPrior.tail,
            length :: lengths,
            newAccumulator
          )
        else
          recursive(
            indexLonger + 1,
            0,
            newCurrentLongestLength,
            0 :: lengths.reverse,
            Nil,
            newAccumulator
          )
      }
      else (currentLongestLength, accumulator)

    val (length, indexPairs) = recursive()
    if (indexPairs.nonEmpty)
      Some(
        indexPairs
          .reverse
          .map {
            indexPair =>
              (
                longer.substring(indexPair._1, indexPair._1 + length),
                if (isLeftShorter) indexPair.swap else indexPair
              )
          }
      )
    else None
  }
  else None

第一个最长公用子字符串

longestCommonSubstringsFast的一个注重效率的版本，当只关心第一个LCS而想忽略相同大小的其他LCS时，它提供了提前终止的机会。

def firstLongestCommonSubstring(left: String, right: String): Option[(String, (Int, Int))] =
  if (left.nonEmpty && right.nonEmpty) {
    val isLeftShorter = left.length < right.length
    val (shorter, longer) =
      if (isLeftShorter) (left, right)
      else (right, left)

    @scala.annotation.tailrec
    def recursive(
      indexLonger: Int = 0,
      indexShorter: Int = 0,
      currentLongestLength: Int = 0,
      lengthsPrior: List[Int] = List.fill(shorter.length)(0),
      lengths: List[Int] = Nil,
      accumulator: Option[(Int, Int)] = None
    ): Option[(Int, (Int, Int))] =
      if (indexLonger < longer.length) {
        val length =
          if (longer(indexLonger) != shorter(indexShorter)) 0
          else lengthsPrior.head + 1
        val newAccumulator =
          if (length > currentLongestLength) Some((indexLonger - length + 1, indexShorter - length + 1))
          else accumulator
        if (length < shorter.length) {
          val newCurrentLongestLength =
            if (length > currentLongestLength) length
            else currentLongestLength
          if (indexShorter < shorter.length - 1)
            recursive(
              indexLonger,
              indexShorter + 1,
              newCurrentLongestLength,
              lengthsPrior.tail,
              length :: lengths,
              newAccumulator
            )
          else
            recursive(
              indexLonger + 1,
              0,
              newCurrentLongestLength,
              0 :: lengths.reverse,
              Nil,
              newAccumulator
            )
        }
        else
          recursive(longer.length, 0, length, lengthsPrior, lengths, newAccumulator) //early terminate
      }
      else accumulator.map((currentLongestLength, _))

    recursive().map {
      case (length, indexPair) =>
        (
          longer.substring(indexPair._1, indexPair._1 + length),
          if (isLeftShorter) indexPair.swap else indexPair
        )
    }
  }
  else None

奖励：

最长通用子字符串最终

重构longestCommonSubstringsFast以增加内部实现的可变性，同时在外部保留函数的引用透明性。
在保持功能性和引用透明性的同时（利用实现本身的可变性，有些人认为这种可变性 * 不是 * 有效的功能），进一步消除了每一点低效，执行速度比longestCommonSubstringsFast提高了近三倍。大部分成本降低是通过用单个Array取代一对List实现的。
要轻松查看与longestCommonSubstringsFast、please view this visual diff的区别。

def longestCommonSubstringsUltimate(left: String, right: String): Option[Set[String]] =
  if (left.nonEmpty && right.nonEmpty) {
    val (shorter, longer) =
      if (left.length < right.length) (left, right)
      else (right, left)
    val lengths: Array[Int] = new Array(shorter.length) //mutable

    @scala.annotation.tailrec
    def recursive(
      indexLonger: Int = 0,
      indexShorter: Int = 0,
      currentLongestLength: Int = 0,
      lastIterationLength: Int = 0,
      accumulator: List[Int] = Nil
    ): (Int, List[Int]) =
      if (indexLonger < longer.length) {
        val length =
          if (longer(indexLonger) != shorter(indexShorter)) 0
          else
            if (indexShorter == 0) 1
            else lastIterationLength + 1
        val newLastIterationLength = lengths(indexShorter)
        lengths(indexShorter) = length //mutation
        val newCurrentLongestLength =
          if (length > currentLongestLength) length
          else currentLongestLength
        val newAccumulator =
          if ((length < currentLongestLength) || (length == 0)) accumulator
          else {
            val entry = indexShorter - length + 1
            if (length > currentLongestLength) List(entry)
            else entry :: accumulator
          }
        if (indexShorter < shorter.length - 1)
          recursive(
            indexLonger,
            indexShorter + 1,
            newCurrentLongestLength,
            newLastIterationLength,
            newAccumulator
          )
        else
          recursive(
            indexLonger + 1,
            0,
            newCurrentLongestLength,
            newLastIterationLength,
            newAccumulator
          )
      }
      else (currentLongestLength, accumulator)

    val (length, indexShorters) = recursive()
    if (indexShorters.nonEmpty)
      Some(
        indexShorters
          .map {
            indexShorter =>
              shorter.substring(indexShorter, indexShorter + length)
          }
          .toSet
      )
    else None
  }
  else None
赞(0）分享  回复(0）举报  2022-12-23
uurity8g

uurity8g4#

**更新：**请勿使用下面详述的方法。

我应该多关注OP的明确提供的实现。不幸的是，我被所有其他的答案分散了注意力，使用低效的面向String的比较，并继续提供我自己的优化版本，这些我能够使用Stream和LazyList的喜悦。
我现在添加了一个additional answer（根据StackOverflow的策略），它涵盖了速度更快的Scala函数式解决方案。
以Stream为中心的解决方案可能如下所示：

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.contains(sub)).headOption

这里，substrings 方法返回产生原始字符串的长度递减的子字符串的流，例如，“test”产生“test”、“tes”、“est”、“te”、“es”、...
方法 longestCommonSubstring 获取从字符串 b 中包含的 a 生成的第一个子字符串

赞(0）分享  回复(0）举报  2022-12-23
t0ybt7op

t0ybt7op5#

**更新：**在发布这个答案之后，感谢@Kolmar的反馈，我发现Char索引策略要快得多（至少快了一个数量级）。现在我添加了additional answer（根据StackOverflow的策略），它涵盖了快得多的Scala函数式解决方案。

我本应该多关注OP专门提供的实现。不幸的是，我被所有其他答案分散了注意力，使用了低效的面向String的比较，并继续撕裂，以提供我自己的优化版本，这些我能够使用Stream和LazyList的喜悦。
除了OP的要求之外，我还有几个额外的要求，即编写一个解决方案来查找两个String示例之间的最长公共子字符串（LCS）。

解决方案要求：

1.急切地查找两个String示例之间的 * 第一个 * LCS
1.通过比较更少的String示例最大限度地减少CPU工作量
1.通过生成更少的String示例来最大限度地减少GC工作量
1.最大化Scala的习惯用法，包括使用Scala集合API
第一个目标是捕获一般的搜索策略，该过程从leftString示例开始，从最长的子字符串生成一个有序的子字符串列表（原始String示例本身）到最短例如，如果leftString示例包含“ABCDEF”，应生成String示例的结果列表，并且完全按照以下顺序：

[
  ABCDEF,
  ABCDE, BCDEF,
  ABCD, BCDE, CDEF,
  ABC, BCD, CDE, DEF,
  AB,BC,CD,DE,EF,
  A,B,C,D,E,F
]

接下来，开始遍历left子串示例的列表，一旦在rightString示例内的任何索引处找到特定的left子串示例，就立即停止。当找到left子串示例时，返回该示例。否则，返回未找到匹配的指示。
关于满足解决方案要求#1的“急切”方法，有两点需要特别注意：

  • 找到的left子字符串示例可能出现在rightString示例中的多个索引处。这意味着使用indexOf从rightString示例的开头搜索left子字符串示例与从rightString的结尾搜索left子字符串示例可能会产生不同的索引值示例使用lastIndexOf。
  • rightString示例中也可能出现第二个（不同的）长度相同的left子字符串示例。本实现忽略了这种可能性。

Scala 2.13/Dotty（又名3.0）的解决方案-使用LazyList：

Stream自2.13起已弃用。

def longestCommonSubstring(left: String, right: String): Option[String] =
  if (left.nonEmpty && right.nonEmpty) {
    def substrings(string: String): LazyList[String] = {
      def recursive(size: Int = string.length): LazyList[String] = {
        if (size > 0) {
          def ofSameLength: LazyList[String] =
            (0 to (string.length - size))
              .iterator.to(LazyList)
              .map(offset => string.substring(offset, offset + size))

          ofSameLength #::: recursive(size - 1)
        }
        else
          LazyList.empty
      }

      recursive()
    }

    val (shorter, longer) =
      if (left.length <= right.length)
        (left, right)
      else
        (right, left)
    substrings(shorter).find(longer.contains)
  }
  else
    None

解决方案Scala 2.12及之前版本-使用Stream：

def longestCommonSubstring(left: String, right: String): Option[String] =
  if (left.nonEmpty && right.nonEmpty) {
    def substrings(string: String): Stream[String] = {
      def recursive(size: Int = string.length): Stream[String] = {
        if (size > 0) {
          def ofSameLength: Stream[String] =
            (0 to (string.length - size))
              .toStream
              .map(offset => string.substring(offset, offset + size))

          ofSameLength #::: recursive(size - 1)
        }
        else
          Stream.empty
      }

      recursive()
    }

    val (shorter, longer) =
      if (left.length <= right.length)
        (left, right)
      else
        (right, left)
    substrings(shorter).find(longer.contains)
  }
  else
    None

备注：

  • 提供visual diff between the two versions以快速查看增量
  • 为了涵盖各种边缘情况（例如：提供空的String作为输入），则Option[String]用于函数的返回类型。
  • 在满足解决方案要求#2和#3时，两个String示例中较短的一个被设置为shorter以减少示例化和与String的比较，String比longerString示例长。
  • 在满足解决方案要求#2和#3时，shorter子串示例产生被以相同的大小进行子批处理（通过distinct）。然后将每个子批次添加到LazyList这确保了仅将实际需要的shorter子串示例的示例化提供给longer.contains函数。
赞(0）分享  回复(0）举报  2022-12-23
ee7vknir

ee7vknir6#

我认为带有 for 理解的代码看起来非常清晰和实用。

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

最后一个函数返回Seq[String]，只要结果可能包含几个最大长度相同的子字符串

赞(0）分享  回复(0）举报  2022-12-23
3ks5zfa0

3ks5zfa07#

这个方法怎么样：
1.获取所有子字符串：
左.初始.平面Map（.尾部）
1.按长度倒序排序
. to列表.排序依据（.长度）.反向
1.找到第一个匹配项
.find（右.包含（_））.get
全功能：

def lcs(left: String, right: String) = {
    left.inits.flatMap(_.tails)
      .toList.sortBy(_.length).reverse
      .find(right.contains(_)).get
  }

注意：get永远不会是空的，因为初始字符串排列也包含空字符串，它总是匹配一些东西。

赞(0）分享  回复(0）举报  2022-12-23
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com