求最长公共子序列长度的一个新方法

提出了一个求序列Ｘ最长单调子序列的方法，若Ｘ的长度为ｎ，则此方法所需时间为Ｏ（ｎｌｏｇｎ），空间占用为Ｏ（ｎ）．利用该方法可有效地求出Ｘ，Ｙ两序列最长公共子序列的长度．如果Ｘ的长度为ｍ，Ｙ的长度为ｎ，此时空间占用为Ｏ（ｍ＋ｎ）；若Ｙ中的各个元素在Ｘ中平均重复出现至多常数次，则所需时间为Ｏ（ｍ＋ｎｌｏｇｎ）．作为应用之一，该方法可以用于文本的比较、等级考试录入文本的评测等．