Improved Lower Bounds on the Expected Length of Longest Common Subsequences

George T. Heineman, Chase Miller, Daniel Reichman +3

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 $\ddot{I}ƒ$ converges to…