Задача №114561. Максимальная ширина
У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка \(t\) длины \(m\) и строка \(s\) длины \(n\). Последовательность индексов \(p_1\), \(p_2\), ..., \(p_m\), где \(1 \leq p_1 < p_2 < \ldots < p_m \leq n\), называется хорошей , если \(s_{p_i} = t_i\) для всех \(i\) от \(1\) до \(m\). Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности \(p\).
Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки \(s\) и \(t\) таковы, что хотя бы одна хорошая последовательность точно существует.
Первая строка входных данных содержит два числа \(n\) и \(m\) \((2 \leq m \leq n \leq 200\,000)\) — длины строк \(s\) и \(t\) соответственно.
Во второй строке входных данных задана строка \(s\), состоящая из строчных букв английского алфавита, а в третьей строке задана строка \(t\), состоящая из строчных букв английского алфавита.
Гарантируется, что существует хотя бы одна хорошая последовательность индексов.
Выведите одно число — максимальную ширину хорошей последовательности.
В первом примере из условия существуют две хорошие последовательности с шириной \(3\): это \(\{1, 2, 5\}\) и \(\{1, 4, 5\}\).
Во втором примере из условия хорошая последовательность максимальной ширины — это \(\{1, 5\}\).
В третьем примере из условия есть лишь одна хорошая последовательность — это \(\{1, 2, 3, 4, 5\}\).
В четвёртом примере из условия есть лишь одна хорошая последовательность — это \(\{1, 2\}\).
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на первых \(40\) тестах будут доступны во время соревнования. Результаты работы на остальных \(10\) будут доступны после окончания соревнования.
Решения, корректно работающие при \(n, m \leq 5\), будут набирать не менее \(20\) баллов.
Решения, корректно работающие при \(n, m \leq 100\), будут набирать не менее \(40\) баллов.
Решения, корректно работающие при \(n, m \leq 1000\), будут набирать не менее \(60\) баллов.
Решения, корректно работающие когда строка \(t\) состоит только из символов « a », будут набирать не менее \(20\) баллов.
5 3 abbbc abc
3
5 2 aaaaa aa
4
5 5 abcdf abcdf
1
2 2 ab ab
1