Here's a hint: look very closely at line 28 of the JavaScript version—particularly the last character of the line. That's where your implementation differs. (You also don't reset l
to zero for every pair of indices, but that's not the most important problem.)
Here's a var
-free Scala version, by the way:
def similarText(x: String, y: String): Int = {
val indices = for {
(s, p) <- x.tails.zipWithIndex
(t, q) <- y.tails.zipWithIndex
l = ((s zip t) takeWhile Function.tupled(_ == _)).size
} yield (p, q, l)
val (pos1, pos2, max) = indices.maxBy(_._3)
if (max == 0) max else max +
similarText(x take pos1, y take pos2) +
similarText(x drop (pos1 + max), y drop (pos2 + max))
}
This is fairly off-the-cuff—I'm sure you could make it more concise and efficient pretty easily.
And for extra credit: there's a bug in the JavaScript version—try for example "aabcd"
and "abcabcd"
and the result won't be the same as PHP's (or mine).