文字列$s$,$t$が与えられる。
最初、文字列集合$A=${$s$},$B=\phi$とする。
このとき、次の操作をできるだけたくさん行いたい。
"abac"の部分列は、
{ "" , "a" , "b" , "c" , "aa" ,"ab" , "ac" , "ba" , "bc" , "aac" , "aba" , "abc" , "bac" , "abac" }
である。
"a"は"abac"の1文字目、または3文字目を抜き出すことによってできた部分列である。
"ac"は"abac"の1文字目と4文字目、または3文字目と4文字目を抜き出すことによってできた部分列である。
入力は以下の形式で与えられる。
$s$ $t$
1行目に文字列$s$,2行目に文字列$t$が与えられる。
入力は以下の条件を満たす。
操作回数の最大値を出力せよ。
AABABCAC A
2
1回目の操作は、$A=${ "AABABCAC" }で始まる。
step1では、$u=$"AABABCAC"に対して、例えば4番目の文字を$t$と等しい部分列として選び、"AAB"と"BCAC"に分割し、それらを$B$に追加する。
step2では、$A$を$B$に置き換え、$B$を空にし、操作回数は1となる。
2回目の操作は、$A=${ "AAB" , "BCAC" }で始まる。
step1では、$u=$"AAB"に対して、例えば1番目の文字を$t$と等しい部分列として選び、""と"AB"に分割し、それらを$B$に追加する。次に$u=$"BCAC"に対して、3番目の文字を$t$と等しい部分列として選び、"BC"と"C"に分割し、それらを$B$に追加する。
step2では、$A$を$B$に置き換え、$B$を空にし、操作回数は2となる。
3回目の操作は、$A=${ "" , "AB" , "BC" , "C" }で始まる。
step1では、$u=$""に対して、$t$と等しい部分列が存在しないため、ここで操作を終了する。
この例の場合、3回目の操作ではstep1で操作が終了したため、操作回数は2となる。
abaabbabaabaabbabbabaabbab ab
3
AbCdEfG aBcDeFg
0