Longest common subsequences between words of very unequal length

2020/09/12 by Bukh, Boris, Zichao Dong, Dong, Zichao
Computer Science · Mathematics · #60C05 #60J05 #60K35 #Advanced Combinatorial Mathematics #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.2009.05869

openalex publication_date 2020/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the expected length of the longest common subsequence between two random words of lengths n and (1-ε)kn over k-symbol alphabet. It is well-known that this quantity is asymptotic to γ_k,ε n for some constant γ_k,ε. We show that γ_k,ε is of the order 1-cε² uniformly in k and ε. In addition, for large k, we give evidence that γ_k,ε approaches 1-\tfrac14ε², and prove a matching lower bound.

Citations

• On the Limiting Shape of Young Tableaux Associated With Inhomogeneous Random Words

Related

• Expected length of the longest common subsequence for large alphabets
• Expected Length of the Longest Common Subsequence of Multiple Strings
• On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words
• Longest common subsequences in sets of words
• Length of the longest common subsequence between overlapping words