017最长公共子字符串.md

最长公共子字符串

算法核心

这是动态规划的常见场景。

如果a[i] = b[j]，那么他们的的最长公共子字符串就是result[i-1, j-1] + 1，否则就是max(result[i-1, j], result[i, j-1])，如果i = 0或j = 0那么result[i, j]就是0。

因此算法也比较好理解，也很好实现。

实现最长公共字符串

def max_sub_string(a, b):
  # a, the first string
  # b, the second string

  result = [[0 for x in range(len(a)+1)] for x in range(len(b)+1)]

  for i in range(len(a)):
    for j in range(len(b)):

      if i == 0 or j == 0:
          result[i][j] = 0
      elif a[i] == b[j]:
        result[i+1][j+1] = result[i][j] + 1
      else:
        result[i+1][j+1] = max(result[i][j+1], result[i+1][j])

  print(result)
  return result

a = 'ABCBDAB'
b = 'BDCABA'
max_sub_string(a, b)