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

A new algorithm for finding length of the longest common subsequence

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

In this paper, a new algorithm for finding the longest monotonic subsequence of a string X was presented. The new algorithm requires O(n log n ) time and O(n) space if the length of the string X is n . By the new algorithm, the length of the longest common subsequence of strings X and Y can be found effectively and O(m+n) space is required. If the elements of Y appears in X by constant number, the algorithm requires O(m+n log n ) time. As an application, the algorithm can be used in comparison of text files and scoring the input text of an examinee.