求最长公共子序列长度的一个新方法 |
| |
作者姓名: | 林清波 吴锤红 |
| |
作者单位: | [1]福建农业大学基础部 [2]福建农业大学网络中心 |
| |
摘 要: | 提出了一个求序列X最长单调子序列的方法,若X的长度为n,则此方法所需时间为O(nlogn),空间占用为O(n),利用该方法可有效地求出X,Y两序列最长公共子序列的长度。如果X的长度为m,Y的长度为n,此时空间占用为O(m+n);若Y中的各个元素在X中平均重复出现至多常数次,则所需时间为O(m+nlogn)。作为应用之一,该方法可以用于文体的比较,等级考试录入文本的评测等。
|
关 键 词: | 最长单调子序列 最长公共子序列 动态选择树 |
本文献已被 维普 等数据库收录! |
|