  In the problem of the longest common substring with $k$ mismatches we are
given two strings $X, Y$ and must find the maximal length $\ell$ such that
there is a length-$\ell$ substring of $X$ and a length-$\ell$ substring of $Y$
that differ in at most $k$ positions. The length $\ell$ can be used as a robust
measure of similarity between $X, Y$. In this work, we develop new
approximation algorithms for computing $\ell$ that are significantly more
efficient that previously known solutions from the theoretical point of view.
Our approach is simple and practical, which we confirm via an experimental
evaluation, and is probably close to optimal as we demonstrate via a
conditional lower bound.
