最长公共子序列算法的分析与实现

本文首先分析最长公共子序列的特点,利用动态规划法求出最长公共子序列的长度数组和状态数组并通过矩阵搜索求出所有有效的跳跃点,构造了求解所有最长公共子序列的算法并通过程序给予实现。算法能有效避免重复搜索,时间效率大大提高,特别适用于基因工程中的基因片段分析。

Analysis and Implementation on Longest Common Subsequence Algorithm

This paper first analyzes the characteristics of the longest common subsequence, then calculates the length of the longest common subsequence using dynamic programming method and constructes an alogorithm for seeking all the longest common subsequence. The algothrm use the matrix search method to find all valid jump point and implemented by program. Algorithm can effectively avoid the duplication of search and time efficiency is greatly improved, especially suitable for the gene fragment analysis in genetic engineering.