# input: a[0..M) and b[0..N), M>=0 and N>=0
#
# output: length of a longest common subsequence of a[0..M) and
#         b[0..N)
#
# O(MN) time and space solution

def lcs_tab(a,b):
  M,N = len(a),len(b)
  tab = [ [ 0 for n in range(N+1) ] for m in range(M+1) ]
  m,n = 1,1
  while m!=M+1:
    if n==N+1: m,n = m+1,1
    else:
      if a[m-1]==b[n-1]: tab[m][n] = 1+tab[m-1][n-1]
      else: tab[m][n] = max(tab[m][n-1],tab[m-1][n])
      n += 1
  return tab[M][N]