Improved Lower Bounds on the Expected Length of Longest Common
Subsequences
Improved Lower Bounds on the Expected Length of Longest Common
Subsequences
It has been proven that, when normalized by $n$, the expected length of a longest common subsequence of $d$ random strings of length $n$ over an alphabet of size $\sigma$ converges to some constant that depends only on $d$ and $\sigma$. These values are known as the Chv\'{a}tal-Sankoff constants, and …