一、最长公共子串和最长公共子序列的区别

最长公共子串：要求子串在原字符串中是连续出现的。   ADE 和ABCDE的最长公共子串是DE

最长公共子序列：不要求子序列在原字符串中是连续的。ADE 和ABCDE的最长公共子序列是ADE

二、最长公共子串

字符串1：caba

字符串2：bab

思路：

1.用一个二维数组存储两个字符串的字符是否相等。对角线上连续为1 的最长的序列即为最长公共子串。

2.如何寻找对角线上连续为1的最长序列？

数组中存储的每一元素的取值为：

若匹配成功，值为1加上 该元素的左上元素的取值（即上一行中的左邻元素）

若匹配不成功，取值为0

最长公共子串