  Longest Common Subsequence ($LCS$) deals with the problem of measuring
similarity of two strings. While this problem has been analyzed for decades,
the recent interest stems from a practical observation that considering single
characters is often too simplistic. Therefore, recent works introduce the
variants of $LCS$ based on shared substrings of length exactly or at least $k$
($LCS_k$ and $LCS_{k+}$ respectively). The main drawback of the
state-of-the-art algorithms for computing $LCS_k$ and $LCS_{k+}$ is that they
work well only in a limited setting: they either solve the average case well
while being suboptimal in the pathological situations or they achieve a good
worst-case performance, but fail to exploit the input data properties to speed
up the computation. Furthermore, these algorithms are based on non-trivial data
structures which is not ideal from a practitioner's point of view. We present a
single algorithm to compute both $LCS_k$ and $LCS_{k+}$ which outperforms the
state-of-the art algorithms in terms of runtime complexity and requires only
basic data structures. In addition, we implement an algorithm to reconstruct
the solution which offers significant improvement in terms of memory
consumption. Our empirical validation shows that we save several orders of
magnitude of memory on human genome data. The C++ implementation of our
algorithms is made available at: https://github.com/google/fast-simple-lcsk
