V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
cheesea
V2EX  ›  问与答

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

  •  
  •   cheesea · 2018-02-16 20:33:14 +08:00 · 2290 次点击
    这是一个创建于 2457 天前的主题,其中的信息可能已经有所发展或是发生改变。

    状态转移方程 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,这不就错了吗?

    9 条回复    2018-02-16 23:48:59 +08:00
    lechain
        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
    873681136
        2
    873681136  
       2018-02-16 20:55:35 +08:00 via iPhone
    LCS (abc, ab) = ab, len = 2
    LCS (abce, abe) = abe, len = 3
    难道不对?
    geelaw
        3
    geelaw  
       2018-02-16 20:56:21 +08:00 via iPhone
    第一个问题在于,我觉得您混淆了 0-based 和其他 1-based 的记号,让人很难理解您的疑问。

    第二件事儿是 LCS 可以表示 子序列 或者 子串,这是两个不同的问题,不要混淆。
    nazor
        4
    nazor  
       2018-02-16 20:56:53 +08:00 via iPhone
    子串和子序列不一样,子串 dp(2)(1)=0
    messyidea
        5
    messyidea  
       2018-02-16 21:04:16 +08:00
    简化一下一楼的答案:
    L[i, j]表示以 s[i]和 s[j]为结尾的相同子串的最大长度, 而不是 s[1..i]和 s[1..j]的最长公共子串的长度
    cheesea
        6
    cheesea  
    OP
       2018-02-16 21:17:36 +08:00
    @geelaw
    你说的对,我发帖的时候太急了,没去考虑太多。不好意思。
    cheesea
        7
    cheesea  
    OP
       2018-02-16 21:18:28 +08:00
    @lechain
    @messyidea
    谢谢!我也觉得应该是这样才说得通!
    j2gg0s
        8
    j2gg0s  
       2018-02-16 21:27:36 +08:00
    百度文章个毛线啊,看书 >> 看 wiki > 搜索
    tsaohai
        9
    tsaohai  
       2018-02-16 23:48:59 +08:00 via iPhone
    五楼正解
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2722 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 01:49 · PVG 09:49 · LAX 17:49 · JFK 20:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.