Longest common subsequences between words of very unequal length

Boris Bukh, Zichao Dong

We consider the expected length of the longest common subsequence between two random words of lengths $n$ and $(1-\epsilon )kn$ over $k$-symbol alphabet. It is well-known that th…