浅谈“最长公共子串”问题及优化算法.doc

浅谈最长公共子串问题及优化算法 浙江省瑞安中学 张新华 潘伟达 最长公共子串问题也称作最长公共子序列问题(不要求连续)英文缩写为LCSLongest Common Subsequence其定义是已知一个序列 S 如果分别是两个或多个已知序列的子序列且是所有符合此条件序列中最长的则 S 称为已知序列的最长公共子序列 最长公共子串问题在实际生活中是很具有实用价值的例如它可以描述两段文字之间的相似度即它