Longest Common Subsequence Python 2 function

Question

When I run LCS( 'human', 'chimp' ), I'm getting "h" instead of "hm". When I run LCS( 'gattaca', 'tacgaacta' ), I'm getting "g" instead of "gaaca". When I run LCS( 'wow', 'whew' ), I'm getting "ww" which is correct. When I run LCS( '', 'whew' ), I'm getting "" which is correct. When I run LCS( 'abcdefgh', 'efghabcd' ), I'm getting "a" instead of "abcd". What am I doing incorrectly?

Here is my code:

def LCS(S, T):
  array = ''
  i = 0
  j = 0
  while i < len(S):
    while j < len(T):
      if S[i] == T[j]:
        array += S[i]
      j += 1
    i += 1
  return array

Answer 1

Figured it out thanks to the people next to me in the lab! It would also be nice to not run into snooty people on Stack Overflow every now and then.

def LCS(S, T):
  # If either string is empty, stop
  if len(S) == 0 or len(T) == 0:
    return ""

  # First property
  if S[-1] == T[-1]:
    return LCS(S[:-1], T[:-1]) + S[-1]

  # Second proprerty
  # Last of S not needed:
  result1 = LCS(S[:-1], T)
  # Last of T not needed
  result2 = LCS(S, T[:-1])
  if len(result1) > len(result2):
    return result1
  else:
    return result2