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"
what happened to findOverlap(“12345”, “01”) ?
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)
}
}
Thanks for that!