Problem:
 Score : 100 points    Problem Statement You are given strings s and t .
Find one longest string that is a subsequence of both s and t .      Notes A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.      Constraints  s and t are strings consisting of lowercase English letters.  1 \leq |s|, |t| \leq 3000         Input Input is given from Standard Input in the following format:  s  t       Output Print one longest string that is a subsequence of both s and t .
If there are multiple such strings, any of them will be accepted.        Sample Input 1 axyb
abyxb      Sample Output 1 axb  The answer is axb or ayb ; either will be accepted.       Sample Input 2 aa
xayaz      Sample Output 2 aa       Sample Input 3 a
z      Sample Output 3   The answer is (an empty string).       Sample Input 4 abracadabra
avadakedavra      Sample Output 4 aaadara

Solution (Python):
from array import array
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [array('L', [0 for j in range(tlen + 1)]) for i in range(slen + 1)]
  for i in range(slen):
    dpi1 = dp[i + 1]
    for j in range(tlen):
      if s[i] == t[j]:
        dpi1[j + 1] = max(dpi1[j + 1], dp[i][j] + 1, dpi1[j], dp[i][j + 1])
      else:
        dpi1[j + 1] = max(dpi1[j + 1], dpi1[j], dp[i][j + 1])
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Solution (Python):
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
    else:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)