[1]殷新春,陈凌.求最长公共子串长度的算法[J].东南大学学报(自然科学版),1998,28(6):191-194.[doi:10.3969/j.issn.1001-0505.1998.06.038]
 Yin Xinchun,Chen Ling.Algorithms for Evaluating Length of the Longest Common Substring[J].Journal of Southeast University (Natural Science Edition),1998,28(6):191-194.[doi:10.3969/j.issn.1001-0505.1998.06.038]
点击复制

求最长公共子串长度的算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
28
期数:
1998年第6期
页码:
191-194
栏目:
计算机科学与工程
出版日期:
1998-11-20

文章信息/Info

Title:
Algorithms for Evaluating Length of the Longest Common Substring
作者:
殷新春陈凌
扬州大学师范学院
Author(s):
Yin Xinchun Chen Ling
Teachers’ College, Yangzhou University, Yangzhou 225002
关键词:
算法 心动阵列 算法分析 最长公共子串
分类号:
TP301.6
DOI:
10.3969/j.issn.1001-0505.1998.06.038
摘要:
给出求2个字符串最长公共子串(LCS)长度的递归算法、递推算法和心动阵列算法.对2个长度分别为n,m(n≥m)的字符串,递归算法的最坏时空复杂性为(m+n)!/(m!n!),而递推算法的时空复杂性分别仅为m+nm+O(1),2m+O(1).在心动阵列算法中,需m个PE和n+m的时间.最后给出了一个应用实例.

相似文献/References:

[1]黄大海.四个魔方构造算法[J].东南大学学报(自然科学版),1989,19(2):66.[doi:10.3969/j.issn.1001-0505.1989.02.010]
 Huang Dahai (Department of Computer Science and Engineering).Four Algorithms for Constructing Magic Squares[J].Journal of Southeast University (Natural Science Edition),1989,19(6):66.[doi:10.3969/j.issn.1001-0505.1989.02.010]
[2]周佩德,谢晶.矢量图文变形的权值拖曳算法研究[J].东南大学学报(自然科学版),1996,26(2):93.[doi:10.3969/j.issn.1001-0505.1996.02.015]
 Zhou Peide,Xie Jing.The Research on Weight-Dragging Algorithms for Deforming Vector Graphics and Text[J].Journal of Southeast University (Natural Science Edition),1996,26(6):93.[doi:10.3969/j.issn.1001-0505.1996.02.015]

更新日期/Last Update: 2013-04-13