Единственное отличие между легкой и сложной версиями — длины строк.
Вам задана строка \(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\).
Выходные данные
Выведите одно целое число — максимально возможную длину подстроки, которую вы можете удалить, чтобы \(t\) осталась подпоследовательностью \(s\).