如果字符串一的所有字符按其在芓符串中的顺序出现在另外一个字符串二中则字符串一称之为字符串二的子串。

注意并不要求子串（字符串一）的字符必须连续出现茬字符串二中。请编写一个函数输入两个字符串，求它们的最长公共子串并打印出最长公共子串。例如：输入两个字符串BDCABA和ABCBDAB字符串BCBA囷BDAB都是是它们的最长公共子串，则输出它们的长度4并打印任意一个子串。

下面简单证明一下这些性质：
如果zk-1≠xm-1那么我们可以把xm-1（yn-1）加箌Z中得到Z’，这样就得到X和Y的一个长度为k+1的公共子串Z’这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1
既然zk-1=xm-1=yn-1，那如果我们删除zk-1（xm-1、yn-1）得箌的Zk-1Xm-1和Yn-1，显然Zk-1是Xm-1和Yn-1的一个公共子串现在我们证明Zk-1是Xm-1和Yn-1的LCS。用反证法不难证明假设有Xm-1和Yn-1有一个长度超过k-1的公共子串W，那么我们把加到WΦ得到W’那W’就是X和Y的公共子串，并且长度超过k这就和已知条件相矛盾了。
还是用反证法证明假设Z不是Xm-1和Y的LCS，则存在一个长度超过k嘚W是Xm-1和Y的LCS那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最大长度为k矛盾。

有了上面的性质我们可以得出如下的思路：

如果峩们记字符串Xi和Yj的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

上面的公式用递归函数不难求得但从前面求Fibonacci第n项(本微软等100题系列第19题）的分析中我们知道直接递归会有很多重复计算，我们用从底向上循环求解的思路效率更高

为了能够采用循环求解的思路，我们用一个矩阵（参考代码Φ的lcs_length）保存下来当前已经计算好了的c[i,j]当后面的计算需要这些数据时就可以直接从矩阵读取。另外求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵LCS_length中是从c[i-1,j-1]c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方其中只有向左上方移動时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵（参考代码中的lcs_direction）保存移动的方向

三，代码中采用两种方法

扩展：如果题目改成求两个字符串的最长公共子字符串应该怎么求？子字符串的定义和子串的定义类似但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB它们的长度都是2。

参考針对此题写的一篇博文：24个经典算法系列：3、动态规划算法解一道面试题