What question did this study set out to answer?

March 4, 2026Bulletin of the Australian Mathematical Society0 citationsOpen Access

Expected Length of the Longest Common Subsequence of Multiple Strings

RLRAY LISanta Clara University WRWILLIAM RENSanta Clara University YWYIRAN WENSanta Clara University

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.

Abstract

Abstract We study the generalised Chvátal–Sankoff constant ₊, ₃, 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 ₂, ₃, establishing that ₂, ₃ = 12 + (1/ {d}). We also derive asymptotically near-optimal bounds on ₊, ₃ for d (k).

AI에게 질문

Bookmark

View Full Paper

Cite This Study

LI et al. (Mon,) studied this question.

synapsesocial.com/papers/69a7cce8d48f933b5eed8bca https://doi.org/https://doi.org/10.1017/s000497272610104x

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

AI에게 질문

Bookmark

View Full Paper