Longest common subsequences in sets of words

2014/06/26 by Boris Bukh, Jie Ma, Bukh, Boris +1 · 1 citation
Computer Science · Mathematics · #05D99 #68R15 #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D99 #msc:68R15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1406.7017

9+epsilon pages, 1 figure

openalex publication_date 2014/06/26 · arxiv created 2014/10/22 · arxiv updated 2014/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a set of t words of length n over a k-letter alphabet, it is proved that there exists a common subsequence among two of them of length at least (n)/(k)+cn^1-1/(t-k-2), for some c>0 depending on k and t. This is sharp up to the value of c.

Citations

• Longest Common Subsequences in Sets of Permutations

Cited by

• Asymptotically half of binary words are shuffle squares

Related

• Longest common subsequences between words of very unequal length
• Expected length of the longest common subsequence for large alphabets
• Most frequent subsequences in a word
• Twins in words and long common subsequences in permutations
• Longest Common Subsequences in Sets of Permutations