论文标题
长度不平等的单词之间的最长共同子序列
Longest common subsequences between words of very unequal length
论文作者
论文摘要
我们考虑了两个长度为$ n $和$ n $和$（1- \ Varepsilon）kn $在$ k $ -symbol字母上的最长常见子序列的预期长度。众所周知，对于某些常数$γ_{k，\ varepsilon} $，该数量渐近至$γ_{k，\ varepsilon} n $。我们表明$γ_{k，\ varepsilon} $是$ 1-c \ varepsilon^2 $均匀的$ k $和$ \ varepsilon $的顺序。此外，对于大$ k $，我们提供证据表明$γ_{k，\ varepsilon} $接近$ 1- \ tfrac {1} {4} {4} \ varepsilon^2 $，并证明了匹配的下限。
We consider the expected length of the longest common subsequence between two random words of lengths $n$ and $(1-\varepsilon)kn$ over $k$-symbol alphabet. It is well-known that this quantity is asymptotic to $γ_{k,\varepsilon} n$ for some constant $γ_{k,\varepsilon}$. We show that $γ_{k,\varepsilon}$ is of the order $1-c\varepsilon^2$ uniformly in $k$ and $\varepsilon$. In addition, for large $k$, we give evidence that $γ_{k,\varepsilon}$ approaches $1-\tfrac{1}{4}\varepsilon^2$, and prove a matching lower bound.
