Longest Common Subsequences in Sets of Words
Longest Common Subsequences in Sets of Words
Given a set of $t\ge k+2$ 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}+cn^{1-1/(t-k-2)}$ for some $c>0$ depending on $k$ and $t$. This is sharp up to the value of $c$.