This analysis derives bounds for the longest common subsequence length in random strings, suggesting improved predictions for multiple sequences.
We study the generalised Chvátal–Sankoff constant γ k,d , which represents the normalised expected length of the longest common subsequence of d independent uniformly random strings over an alphabet of size k . We derive asymptotically tight bounds for γ 2,d , establishing that γ 2,d = 12 + Θ (1/√d) . We also derive asymptotically near-optimal bounds on γ k,d for d≥ Ω (log k) .
No takes yet. Share an insight, caveat, or question.
LI et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: