Merging overlapping strings

Question

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 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)
}

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

Answer 1

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
}

And with that mergeOverlap is just

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

And some tests of this implementation:

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