# 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 O(N) space solution

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