Longest common subsequences in sets of words

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 $\frac{n}{k}+c{n}^{1-1/(t-k-2)}$, for some $c>0$ depending on $k$ and $t$. This is sharp up to the value of $c$.

9+epsilon pages, 1 figure

References in corpus (1)

• Longest Common Subsequences in Sets of Permutations