Javascript function to find the overlap between two strings

Finding where two strings overlap is an interesting programming problem, easily solved recursively.

This is a common problem in some parts of computer science, for instance DNA processing, which takes many small strands of DNA and re-combines them by finding the bits that overlap. It also happens when you’re using subtitles – these can repeat in a subtitle file, especially in the newer formats like WebVTT where you can specify highlighted texts in each time window (highlighting the word being spoken).

function findOverlap(a, b) {
  if (b.length === 0) {
    return "";
  }

  if (a.endsWith(b)) {
    return b;
  }

  if (a.indexOf(b) >= 0) {
    return b;
  }

  return findOverlap(a, b.substring(0, b.length - 1));
}

Some test cases:

findOverlap("12345", "aaa")
""
findOverlap("12345", "12")
"12"
findOverlap("12345", "345")
"345"
findOverlap("12345", "3456")
"345"
findOverlap("12345", "111")
"1"

3 Replies to “Javascript function to find the overlap between two strings”

  1. Hi

    This did not work for the following 2 strings: “buyOpen” and “sellOpen”

    I had to change it as follows:

    function findOverlap(a, b, originalB, reverse) {
    if (!originalB) {
    originalB = b
    }
    if (b.length === 0 && !reverse) { return findOverlap(a, originalB, originalB, true) }
    if (a.endsWith(b)) { return b }
    if (a.indexOf(b) >= 0) { return b }
    if (!reverse) {
    return findOverlap(a, b.substring(0, b.length – 1), originalB, false)
    } else {
    return findOverlap(a, b.substring(1, b.length), originalB, true)
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *