原题
给出两个字符串，找到最长公共子串，并返回其长度。
样例
给出A=“ABCD”
，B=“CBCE”，返回 2
解题思路
- 典型的双序列行动态规划 - Two Sequence DP
- 不同于Longest Common Subsequence, 本题是substring，string要求是连续的，sequence可以是不连续的
- 本题的状态表示类似于Longest Increasing Subsequence
- cache[i][j]表示string1的前i个字符和string2的前j个字符的LCS，注意必须以i/j结尾
cache
完整代码
class Solution:
# @param A, B: Two string.
# @return: the length of the longest common substring.
def longestCommonSubstring(self, A, B):
if not A or not B:
return 0
cache = [[0 for i in range(len(A) + 1)] for i in range(len(B) + 1)]
res = 0
for i in range(1, len(B) + 1):
for j in range(1, len(A) + 1):
if A[j - 1] == B[i - 1]:
cache[i][j] = cache[i - 1][j - 1] + 1
res = max(res, cache[i][j])
return res
