Codeforces Round 579 (Div. 3) |
---|
Закончено |
Единственное отличие между легкой и сложной версиями — длины строк.
Вам задана строка $$$s$$$ и строка $$$t$$$, обе состоят только из строчных букв латинского алфавита. Гарантируется, что $$$t$$$ может быть получена из $$$s$$$ при помощи удаления некоторого (возможно, нулевого) количества символов (не обязательно последовательных) из $$$s$$$ без изменения порядка оставшихся символов (другими словами, гарантируется, что $$$t$$$ является подпоследовательностью $$$s$$$).
Например, строки «test», «tst», «tt», «et» и «» являются подпоследовательностями строки «test». А строки «tset», «se», «contest» не являются подпоследовательностями строки «test».
Вы хотите удалить некоторую подстроку (последовательную подпоследовательность) из $$$s$$$ максимально возможной длины таким образом, чтобы после удаления этой подстроки $$$t$$$ все еще осталась подпоследовательностью $$$s$$$.
Если вы хотите удалить подстроку $$$s[l;r]$$$, то строка $$$s$$$ примет вид $$$s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$$$ (где $$$|s|$$$ равно длине $$$s$$$).
Ваша задача — найти максимально возможную длину подстроки, которую вы можете удалить, чтобы $$$t$$$ осталась подпоследовательностью $$$s$$$.
Первая строка входных данных содержит одну строку $$$s$$$, состоящую из не менее $$$1$$$ и не более $$$2 \cdot 10^5$$$ строчных букв латинского алфавита.
Вторая строка входных данных содержит одну строку $$$t$$$, состоящую из не мене $$$1$$$ и не более $$$2 \cdot 10^5$$$ строчных букв латинского алфавита.
Гарантируется, что $$$t$$$ является подпоследовательностью $$$s$$$.
Выведите одно целое число — максимально возможную длину подстроки, которую вы можете удалить, чтобы $$$t$$$ осталась подпоследовательностью $$$s$$$.
bbaba bb
3
baaba ab
2
abcde abcde
0
asdfasdf fasd
3
Название |
---|