Заданы две строки \(s\) и \(t\). За один ход можно выбрать произвольную из двух строк и удалить её первый (самый левый) символ. При этом длина строки уменьшается на \(1\).
Например:
- применив ход к строке «where», в результате получится строка «here»,
- применив ход к строке «a», в результате получится пустая строка «».
Требуется сделать две строки равными, выполнив наименьшее количество ходов, применяя каждый раз ход к любой из двух строк. Это допустимо, что в итоге обе строки окажутся равны пустой строке и равны между собой. В этом случае, очевидно, ответ — это сумма длин заданных строк.
Напишите программу, которая найдет минимальное количество ходов, чтобы сделать две заданные строки \(s\) и \(t\) равными.
Выходные данные
Выведите искомое наименьшее количество ходов. Возможно, что в итоге обе строки окажутся равны пустой строке и равны между собой. В этом случае, очевидно, ответ — это сумма длин заданных строк.
Примечание
В первом примере следует один раз применить ход к первой строке и один раз применить ход ко второй строке. В результате обе строки будут равны «est».
Во втором примере ход следует применить \(8\) раз к «codeforces». В результате будет получена строка «codeforces» \(\to\) «es». К строке «yes» ход следует применить один раз. В результате будет получена такая же строка «yes» \(\to\) «es».
В третьем примере строки можно сделать равными только полностью их удалив. То есть в итоге обе строки получатся пустыми.
В четвёртом примере следует удалить первый символ второй строки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
test
west
|
2
|
|
2
|
codeforces
yes
|
9
|
|
3
|
test
yes
|
7
|
|
4
|
b
ab
|
1
|