[classic] LCA Longest Common Subsring | 两个string的最长公共substring

Posted by: lexigrey on: October 12, 2013

• In: classic | summery
• Leave a Comment

比如abcdefg, defmnabs，最长公共subtring是def。

又是二维DP求String的最优解。居然还是算法课作业做过，真是一点印象也木有了。

• d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
• d[i][j] =
  1. A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
  2. A[i] != B[j] : d[i][j] = 0//断开了，无公共后缀了

总结一下二维DP解String题的做法：

• 一个String, d[i][j]表示A[i…j]的某个最优解
• 两个String, d[i][j]表示A[0…i], B[0…j]的某个比较方式的最优解

Tags: 2WayDP, EndWith, string