转移方程 f[i][j] = f[i - 1][j - 1] + 1
image
def longestCommonSubstring(self, A, B):
# write your code here
n = len(A)
m = len(B)
if n == 0 or m == 0:
return 0
f = [[0 for col in range(m)] for row in range(n)]
maxsub = 0
for i in range(n):
f[i][0] = 0
if A[i] == B[0]:
f[i][0] = 1
maxsub = 1
for j in range(1,m):
f[0][j] = 0
if A[0] == B[j]:
f[0][j] = 1
maxsub = 1
for i in range(1,n):
for j in range(1,m):
if A[i] == B[j]:
f[i][j] = f[i-1][j-1]+1
else:
f[i][j] = 0
maxsub = max(maxsub, f[i][j])
return maxsub
