D2. Удалите подстроку (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между легкой и сложной версиями — длины строк.

Вам задана строка $$$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