У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t
длины m
и строка s
длины n
. Последовательность индексов p1
, p2
, ..., pm
, где 1<=p1
<p2
<…<pm<=n
, называется хорошей , если spi=ti
для всех i
от 1
до m
. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p
.
Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки s
и t
таковы, что хотя бы одна хорошая последовательность точно существует.
Входные данные
Первая строка входных данных содержит два числа n
и m
(2<=m<=n<=200000) - длины строк s
и t
соответственно.
Во второй строке входных данных задана строка s
, состоящая из строчных букв английского алфавита, а в третьей строке задана строка t
, состоящая из строчных букв английского алфавита.
Гарантируется, что существует хотя бы одна хорошая последовательность индексов.
Выходные данные
Выведите одно число - максимальную ширину хорошей последовательности.
Примечание
В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.
Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.
В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.
В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
5 3
abbbc
abc
|
3
|
2 |
5 2
aaaaa
aa
|
4
|
3 |
5 5
abcdf
abcdf
|
1
|
4 |
2 2
ab
ab
|
1
|