Expected Length of the Longest Common Subsequence of Multiple Strings
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916689082318848 |
|---|---|
| author | Li, Ray Ren, William Wen, Yiran |
| author_facet | Li, Ray Ren, William Wen, Yiran |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10425 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Expected Length of the Longest Common Subsequence of Multiple Strings Li, Ray Ren, William Wen, Yiran Combinatorics Discrete Mathematics Probability 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)$. |
| title | Expected Length of the Longest Common Subsequence of Multiple Strings |
| topic | Combinatorics Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2504.10425 |