Слияние перекрывающихся строк

Question

Предположим, мне нужно объединить две перекрывающиеся строки следующим образом:

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

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

Я могу написать эту функцию, используя ответ на один из моих предыдущих вопросов:

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?

Answer 1

Это не хвостовая рекурсия, но это очень простой алгоритм.

def mergeOverlap(s1: String, s2: String): String =
  if (s2 startsWith s1) s2
  else s1.head +: mergeOverlap(s1.tail, s2)

Answer 2

Вы можете найти перекрытие между двумя строками во времени, пропорциональное общей длине строк O (n + k) , используя алгоритм для вычисления функции префикса . Префиксная функция строки с индексом i определяется как размер самого длинного суффикса с индексом i, который равен префиксу всей строки (исключая тривиальный случай).

См. Эти ссылки для более подробного объяснения определения и алгоритма его вычисления:

• https://cp-algorithms.com/string/prefix-function.html
• https://hyperskill.org/learn/step/6413#a -определение Префикс-функция

Вот реализация модифицированного алгоритма, который вычисляет самый длинный префикс второго аргумента, равный суффиксу первого аргумента:

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