这是一个创建于 2470 天前的主题，其中的信息可能已经有所发展或是发生改变。
状态转移方程 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，这不就错了吗？
 |
1
lechain 2018-02-16 20:44:38 +08:00
某不存在搜索引擎第一个答案：
>> 假设两个字符串分别为 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 |
 |
2
873681136 2018-02-16 20:55:35 +08:00 via iPhone
LCS (abc, ab) = ab, len = 2
LCS (abce, abe) = abe, len = 3 难道不对？ |
 |
3
geelaw 2018-02-16 20:56:21 +08:00 via iPhone
第一个问题在于，我觉得您混淆了 0-based 和其他 1-based 的记号，让人很难理解您的疑问。
第二件事儿是 LCS 可以表示 子序列 或者 子串，这是两个不同的问题，不要混淆。 |
 |
4
nazor 2018-02-16 20:56:53 +08:00 via iPhone
子串和子序列不一样，子串 dp(2)(1)=0
|
 |
5
messyidea 2018-02-16 21:04:16 +08:00
简化一下一楼的答案：
L[i, j]表示以 s[i]和 s[j]为结尾的相同子串的最大长度， 而不是 s[1..i]和 s[1..j]的最长公共子串的长度 |
 |
8
j2gg0s 2018-02-16 21:27:36 +08:00
百度文章个毛线啊，看书 >> 看 wiki > 搜索
|
 |
9
tsaohai 2018-02-16 23:48:59 +08:00 via iPhone
五楼正解
|
Select Language