合并重叠的字符串

假设我需要合并两个重叠的字符串，如下所示：

def mergeOverlap(s1: String, s2: String): String = ???

mergeOverlap("", "")       // ""
mergeOverlap("", "abc")    // abc  
mergeOverlap("xyz", "abc") // xyzabc 
mergeOverlap("xab", "abc") // xabc

我可以使用以下函数编写这个函数answer https://stackoverflow.com/a/25105780/521070我之前的问题之一：

def mergeOverlap(s1: String, s2: String): String = { 
  val n = s1.tails.find(tail => s2.startsWith(tail)).map(_.size).getOrElse(0)
  s1 ++ s2.drop(n)
}

你能建议一下吗either更简单的or也许更有效地实施mergeOverlap?

您可以在与字符串总长度成正比的时间内找到两个字符串之间的重叠O(n + k)使用算法来计算前缀函数 https://cp-algorithms.com/string/prefix-function.html。索引处字符串的前缀函数i定义为索引处最长后缀的大小i等于整个字符串的前缀（不包括简单的情况）。

有关定义和计算算法的更多说明，请参阅这些链接：

• https://cp-algorithms.com/string/prefix-function.html https://cp-algorithms.com/string/prefix-function.html
• https://hyperskill.org/learn/step/6413#a-definition-of-the-prefix-function https://hyperskill.org/learn/step/6413#a-definition-of-the-prefix-function

下面是修改算法的实现，它计算第二个参数的最长前缀，等于第一个参数的后缀：

import scala.collection.mutable.ArrayBuffer

def overlap(hasSuffix: String, hasPrefix: String): Int = {
  val overlaps = ArrayBuffer(0)
  for (suffixIndex <- hasSuffix.indices) {
    val currentCharacter = hasSuffix(suffixIndex)
    val currentOverlap = Iterator.iterate(overlaps.last)(overlap => overlaps(overlap - 1))
      .find(overlap =>
        overlap == 0 ||
        hasPrefix.lift(overlap).contains(currentCharacter))
      .getOrElse(0)
    val updatedOverlap = currentOverlap +
      (if (hasPrefix.lift(currentOverlap).contains(currentCharacter)) 1 else 0)
    overlaps += updatedOverlap
  }
  overlaps.last
}

就这样mergeOverlap只是

def mergeOverlap(s1: String, s2: String) = 
  s1 ++ s2.drop(overlap(s1, s2))

以及此实现的一些测试：

scala> mergeOverlap("", "")    
res0: String = ""

scala> mergeOverlap("abc", "")
res1: String = abc

scala> mergeOverlap("", "abc")
res2: String = abc

scala> mergeOverlap("xyz", "abc")
res3: String = xyzabc

scala> mergeOverlap("xab", "abc")
res4: String = xabc

scala> mergeOverlap("aabaaab", "aab")
res5: String = aabaaab

scala> mergeOverlap("aabaaab", "aabc")
res6: String = aabaaabc

scala> mergeOverlap("aabaaab", "bc")
res7: String = aabaaabc

scala> mergeOverlap("aabaaab", "bbc")
res8: String = aabaaabbc

scala> mergeOverlap("ababab", "ababc")
res9: String = abababc

scala> mergeOverlap("ababab", "babc")
res10: String = abababc

scala> mergeOverlap("abab", "aab")
res11: String = ababaab