# 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)
#
# exponential (in N and M) naive solution

def lcs_naive(a,b):
  return lcs_aux(a,b,len(a),len(b))

def lcs_aux(a,b,m,n):
  ans = None
  if m==0 or n==0: ans = 0
  else:
    if a[m-1]==b[n-1]: ans = 1+lcs_aux(a,b,m-1,n-1)
    else: ans = max(lcs_aux(a,b,m,n-1),lcs_aux(a,b,m-1,n))
  return ans