摘要
文章分析了LCS问题的最优子结构性质,建立了求最优值的递归关系式。在此基础上,进一步分析、总结、归纳,指出了LCS的长度具有的性质及相关定理。设计了一种高效LCS算法,与现有算法相比,该算法空间复杂度非常低、时间复杂度较低。
This paper analyzes nature of optimal substructure for the LCS problem, and establishes the recursion formula to get the optimal value. Through further analysis, many natures and theorems for the LCS problem are summarized and a high-efficient algorithm of LCS is designed in this paper. It＇ s space and time complexities are lower than the existing algorithms.
出处
《南阳理工学院学报》
2013年第6期61-64,共4页
Journal of Nanyang Institute of Technology
基金
国家自然科学基金项目(90818013)
浙江理工大学基金项目(yb07002)
关键词
最长公共子序列
最优子结构
递归关系
高效
longest common subsequence
optimal substructure
recursive relation
high efficiency
