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

摘要

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