算法分析系列文章中的代码可被任何人无偿使用于任何场景且无需注明来源也不必在使用前征得本文作者同意。
算法分析系列文章旨在传播准确、完整、简洁、易懂、规范的代码实现,并传授基本的编程思想和良好的编码习惯与技巧。
若文章中的代码存在问题或逻辑错误,请通过邮件等形式(见文章结尾)告知于本文作者以便及时修正错误或改进代码。
算法系列文章不可避免地会参考和学习众多网友的成果,在行文风格、内容及求解思路上也会进行借鉴,如有侵权嫌疑,请联系本文作者。
PS:若为转载该文章,请务必注明来源,本站点欢迎大家转载。
问题描述
如果序列 中的所有元素按照其在 中的出现顺序依次出现在另一个序列 中,则称 为 的子序列。
子序列不要求位置的连续性(即,元素相邻),只要相对顺序不变即可。
若给定一个序列集合(数量大于或等于2,但通常为两个序列),则这些序列所共同拥有的子序列,称为公共子序列。而在这些公共子序列中长度最长的子序列则称为该序列集合的最长公共子序列(Longest Common Sequence, LCS)。
本例所要求的便是求解任意两个序列的最长公共子序列(可能存在多个不同的序列),并打印其长度及其其中的任意一个序列。