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

[cheesea]

状态转移方程 dp[i][j] = 1 + dp[i-1][j-1] if str1[i] == str[j]，这里的 dp[i][j]具体是代表什么？ 百度几乎所有文章都说 dp[i][j]表示 str1[1..i]和 str2[1..j]的最长公共子串的长度，但是这明显是不对的， 如果有 str1 = "abce", str2 = "abe"， 那么按对 dp 的定义，有 dp[2][1] = 2，此时 str1[3] = str2[2], dp[3][2] = dp[2][1] + 1 = 3，这不就错了吗？

[lechain]

某不存在搜索引擎第一个答案：
>> 假设两个字符串分别为 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

[873681136]

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

[geelaw]

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

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

[nazor]

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

[messyidea]

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

[cheesea]

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

[cheesea]

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

[j2gg0s]

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

[tsaohai]

五楼正解