最长公共子串 LCS 的一个疑问？

某不存在搜索引擎第一个答案：
>> 假设两个字符串分别为 s 和 t，s[i]和 t[j]分别表示其第 i 和第 j 个字符(字符顺序从 0 开始)，再令 L[i, j]表示以 s[i]和 s[j]为结尾的相同子串的最大长度。应该不难递推出 L[i, j]和 L[i+1,j+1]之间的关系，因为两者其实只差 s[i+1]和 t[j+1]这一对字符。若 s[i+1]和 t[j+1]不同，那么 L[i+1, j+1]自然应该是 0，因为任何以它们为结尾的子串都不可能完全相同；而如果 s[i+1]和 t[j+1]相同，那么就只要在以 s[i]和 t[j]结尾的最长相同子串之后分别添上这两个字符即可，这样就可以让长度增加一位。合并上述两种情况，也就得到 L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。
source： http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html

LCS (abc, ab) = ab, len = 2
LCS (abce, abe) = abe, len = 3
难道不对？

第一个问题在于，我觉得您混淆了 0-based 和其他 1-based 的记号，让人很难理解您的疑问。

第二件事儿是 LCS 可以表示 子序列 或者 子串，这是两个不同的问题，不要混淆。

子串和子序列不一样，子串 dp(2)(1)=0

简化一下一楼的答案：
L[i, j]表示以 s[i]和 s[j]为结尾的相同子串的最大长度， 而不是 s[1..i]和 s[1..j]的最长公共子串的长度

@geelaw
你说的对，我发帖的时候太急了，没去考虑太多。不好意思。

@lechain
@messyidea
谢谢！我也觉得应该是这样才说得通！

百度文章个毛线啊，看书 >> 看 wiki > 搜索

五楼正解