其中最长的那个就叫做“最长公共子序列”。
随机产生两个长度为n的01序列，其中数字1出现的概率是p，数字0出现的概率是1…p。用cp（n）来表示它们的最长公共子序列的长度，用cp来表示cp（n）/n的极限值。
关于cp的存在性，有一个非常巧妙的证明；然而，这个证明仅仅说明了cp的存在性，它完全没有给计算cp带来任何有用的提示。
即使是c1/2的值，也没人能成功算出来。michaelsteele猜想c1/2=2/（1＋√2）≈0。828427。后来，v。chvatal和d。sankoff证明了……，看上去michaelsteele的猜想似乎很可能是对的。2003年，geelueker证明了0。7880