Expected Length of the Longest Common Subsequence of Multiple Strings

Key Points

• The aim is to analyze the expected length of the longest common subsequence in multiple random strings.
• Examined the generalized Chvátal–Sankoff constant for independent random strings.
• Derived asymptotic bounds for specific cases of the constant.
• Analyzed scenarios with varying alphabet sizes.
• Established that the constant for two strings, gamma_2,d, is 1/2 plus a correction term proportional to 1/sqrt(d).
• Identified key bounds for gamma_k,d when the number of strings is large relative to log of the alphabet size.