| 求最长公共子序列长度的一个新方法 |
| |
| 引用本文： | 林清波,吴锤红.求最长公共子序列长度的一个新方法[J].福建农林大学学报(自然科学版),1998(4). |
| |
| 作者姓名： | 林清波 吴锤红 |
| |
| 作者单位： | 福建农业大学基础部(林清波)，福建农业大学网络中心(吴锤红) |
| |
| 摘 要： | 提出了一个求序列Ｘ最长单调子序列的方法，若Ｘ的长度为ｎ，则此方法所需时间为Ｏ（ｎｌｏｇｎ），空间占用为Ｏ（ｎ）．利用该方法可有效地求出Ｘ，Ｙ两序列最长公共子序列的长度．如果Ｘ的长度为ｍ，Ｙ的长度为ｎ，此时空间占用为Ｏ（ｍ＋ｎ）；若Ｙ中的各个元素在Ｘ中平均重复出现至多常数次，则所需时间为Ｏ（ｍ＋ｎｌｏｇｎ）．作为应用之一，该方法可以用于文本的比较、等级考试录入文本的评测等．
|
| 关 键 词： | 最长单调子序列 最长公共子序列 动态选择树 |
A new algorithm for finding length of the longest common subsequence |
| |
| Lin Qingbo,Wu Chuihong.A new algorithm for finding length of the longest common subsequence[J].Journal of Fujian Agricultural and Forestry University,1998(4). |
| |
| Authors: | Lin Qingbo Wu Chuihong |
| |
| Institution: | Lin Qingbo 1 Wu Chuihong 2 |
| |
| Abstract: | 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. |
| |
| Keywords: | longest monotonic subsequence longest common subsequence dynamic selecting tree |
| 本文献已被 CNKI 等数据库收录！ |
