























We study the generalized Chvátal-Sankoff constant $γ_{k,d}$, 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 $γ_{2,d}$, establishing that $γ_{2,d} = \frac{1}{2} + Θ\left(\frac{1}{\sqrt{d}}\right)$. We also derive asymptotically near-optimal bounds on $γ_{k,d}$ for $d\ge Ω(\log k)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。