Longest common subsequences in sets of words

2014/06/26 by Bukh, Boris, Ma, Jie · 1 citation
#05D99 #68R15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1406.7017

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.

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