Posted on

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"