コンテストの解説見たら解けました。 最初は「最適性の原理」に基づいてDPテーブルにおけるdp[i][j]に、0からi-1番目の文字列sと、同じく0からj-1番目の文字列tという2つの文字列のlcs(最長共通部分列)を格納していく方式をとって組んでたらWAは無かったけれ…