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: def solve(s, t):
      # 1-origin
      s_size, t_size = len(s), len(t)
      dp = [[0] * (t_size + 1) for _ in range(s_size + 1)]
  
      for i in range(1, s_size + 1):
          for j in range(1, t_size + 1):
              prev_i, prev_j = i - 1, j - 1
              dp[i][j] = max(dp[prev_i][j], dp[i][prev_j])
              if s[prev_i] != t[prev_j]:
                  # 不一致
                  continue
              if dp[prev_i][prev_j] + 1 <= dp[i][j]:
                  # maxを超えないとき
                  continue
              dp[i][j] = dp[prev_i][prev_j] + 1
  
      # 文字復元
      buff = []
      min_length = 0
      for key in range(t_size + 1):
          if min_length < dp[s_size][key]:
              min_length = dp[s_size][key]
              buff.append(t[key - 1])
      return "".join(buff)
  
  
  def main():
      s, t = input(), input()
  
      ans = solve(s, t)
      print(ans)
  
  
  main()
  
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"}]