合并重叠的字符串

问题描述

假设我需要像这样合并两个重叠的字符串：

Suppose I need to merge two overlapping strings like that:

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

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

I可以使用来回答我以前的问题之一：

I can write this function using the answer to one of my previous questions:

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

您能否建议 一个更简单的或可能更有效地实现 mergeOverlap ？

Could you suggest either a simpler or maybe more efficient implementation of mergeOverlap?

推荐答案

您可以找到两个字符串之间的重叠时间，它们与字符串的总长度成正比 O（n + k），使用算法来计算。索引 i 处的字符串的前缀函数定义为索引 i 处最长后缀的大小，等于

You can find the overlap between two strings in time proportional to the total length of the strings O(n + k) using the algorithm to calculate the prefix function. Prefix function of a string at index i is defined as the size of the longest suffix at index i that is equal to the prefix of the whole string (excluding the trivial case).

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

See those links for more explanation of the definition and the algorithm to compute it:

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

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

Here is an implementation of a modified algorithm that calculates the longest prefix of the second argument, equal to the suffix of the first argument:

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

这篇关于合并重叠的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！