最长公共子序列算法（LCS）

一、问题描述

        LCS算法，找出两个字符串最大匹配子串。

二、解题思路

        设置两个矩阵，一个保存每次字符匹配的最大结果值，一个保存匹配符号。

       

        在按行按列逐个字符匹配的过程中，

       

        若匹配相同，则把上一次匹配的数量值加一（一般是矩阵左上角的数值），同时更新标记矩阵。

        若不匹配，则看不含当前值的附近值（一般是正上方和左边的值）谁大，把最大的移过来。

        最后使用某种数据结构统计匹配上的子字符串（此处用的是list）。

       

        设计缺陷：空间复杂度较高（见下方优化改进）。

三、注意事项

        1.关于匹配时候的遍历，无论从行遍历还是列遍历，都可以，但是前后需要一致。

        2.数组越界问题，一般是从字符串开头到结尾没有处理好。

        3.最好打印出这两个矩阵，方便调试。

        4.字符串是倒着找的，需要逆序输出。

四、优化改进

        设计思路：将两个矩阵简化为一个数组。

        按照原LCS的思路，每次比较值其实只有当前值，当前值的左上角元素，当前值的上方元素，当前值的左边元素四个，这四个值都可以在一维数组中找到代替，本次数组只保存绿色的部分，应注意第一个元素是0，在匹配之前，保存当前值（temp_before）最为后续元素的左上角元素，当前值的上方元素（lcs_opt_matrix[j]）和当前值的左边元素（lcs_opt_matrix[j-1]）。

       

        核心代码实现：

        注意事项：当循环到1时，temp_after的左上角应该是0，而不是上一行的末尾，因此需要重置。

       

        设计缺陷：无法统计出匹配上的子字符串。

       代码实现：USTC_XuYun_alg/lcs