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"

If you want a good Javascript book, I got a lot out of Secrets of the Javascript Ninja.

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

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