EXPECTED LENGTH OF THE LONGEST COMMON SUBSEQUENCE OF MULTIPLE STRINGS

Abstract We study the generalised Chvátal–Sankoff constant $\gamma _{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 $\gamma _{2,d}$ , establishing that $\gamma _{2,d} = \tfrac 12 + \Theta ({1}/{\sqrt {d}})$ . We also derive asymptotically near-optimal bounds on $\gamma _{k,d}$ for $d\ge \Omega (\log k)$ .