A20 - LCS
解説
/
実行時間制限: 10 sec / メモリ制限: 1024 MB
配点: 1000 点
問題文
文字列 S と T が与えられます。
S と T の共通部分列(S の部分列かつ T の部分列)のうち、最長のものは何文字かを出力するプログラムを作成してください。
ただし、ある文字列の 部分列 とは、その文字列から順番を変えずに一部の文字を取り出したものを指します。
たとえば grain
は programming
の部分列です(4, 5, 6, 9, 10 文字目を取り出す)。
制約
- S の文字数は 1 以上 2000 以下
- T の文字数は 1 以上 2000 以下
- S, T は英小文字からなる
入力
入力は以下の形式で標準入力から与えられます。
S T
出力
最長の共通部分列は何文字か、整数で出力してください。
入力例 1
mynavi monday
出力例 1
3
3 文字の文字列 mna
は、mynavi
と monday
両方の部分列となっています。
入力例 2
tokyo kyoto
出力例 2
3