状态转移方程 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
五楼正解
|