output_description: 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.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      s
      t
attempt: s=input()
  t=input()
  n=len(s)
  m=len(t)
  dp=[[0 for i in range(m+1)] for j in range(n+1)]
  ​
  ​
  #メイン
  ​
  #dp[i][j]:=s_1~s_iとt_1~t_jに対するLCSの長さ
  for i in range(n):
      for j in range(m):
          if s[i]==t[j]:
              dp[i+1][j+1]=dp[i][j]+1 #同じならくっつけられる
          else:
              dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
  #print(dp[n][m])
  #dpを逆からたどって文字列を復元
  ans = ''
  while(dp[n][m]>0):
    if dp[n][m] == dp[n-1][m-1] +1 and dp[n][m] == dp[n-1][m] +1 and dp[n][m] == dp[n][m-1] +1:
      ans += s[n-1]
      n -= 1
      m -= 1
    elif dp[n-1][m] > dp[n][m-1]:
      n -= 1
    else:
      m -= 1
  print(''.join(reversed(list(ans))))
problem_description: Statement
  
  You are given strings s and t. Find one longest string that is a subsequence
  of both s and t.
samples: [{"input": "axyb\n    abyxb", "output": "axb\n    \n\nThe answer is `axb` or `ayb`; either will be accepted.\n\n* * *"}, {"input": "aa\n    xayaz", "output": "aa\n    \n\n* * *"}, {"input": "a\n    z", "output": "The answer is `` (an empty string).\n\n* * *"}, {"input": "abracadabra\n    avadakedavra", "output": "aaadara"}]