Задано две строки \(a\) и \(b\), состоящие из строчных латинских букв.
Подпоследовательность строки — это строка, которую можно получить из исходной строки удалением любого количества символов (возможно, ни одного). Подстрока строки — это ее непрерывная подпоследовательность.
Например, рассмотрим строку abac:
- a, b, c, ab, aa, ac, ba, bc, aba, abc, aac, bac и abac — подпоследовательности этой строки;
- a, b, c, ab, ba, ac, aba, bac и abac — подстроки этой строки.
Ваша задача — вычислить минимально возможную длину строки, которая содержит \(a\) в качестве подстроки и \(b\) в качестве подпоследовательности.
Выходные данные
Для каждого набора выведите одно целое число — минимально возможную длину строки, которая содержит \(a\) в качестве подстроки и \(b\) в качестве подпоследовательности.
Примечание
В приведенных ниже примерах подпоследовательность символов, соответствующая строке \(b\), выделена жирным шрифтом.
В первом примере один из возможных ответов — caba.
Во втором примере один из возможных ответов — ercf.
В третьем примере один из возможных ответов — mmm.
В четвертом примере один из возможных ответов — contest.
В пятом примере один из возможных ответов — abcdefg.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
aba
cb
er
cf
mmm
mmm
contest
test
cde
abcefg
|
4
4
3
7
7
|