Expected Length of the Longest Common Subsequence of Multiple Strings

Abstract

We study the generalized Chvátal-Sankoff constant ${\hat{I}}_{k,d}^3$, which represents the normalized expected length of the longest common subsequence (LCS) of $d$ independent uniformly random strings over an alphabet of size $k$. We derive asymptotically tight bounds for ${\hat{I}}_{2,d}^3$, establishing that ${\hat{I}}_{2,d}^3=\frac{1}{2}+\hat{I}˜\left(\frac{1}{\sqrt{d}}\right)$. We also derive asymptotically near-optimal bounds on ${\hat{I}}_{k,d}^3$ for $d\ge \hat{I}\text{c◯}(\log k)$.