Даны две строки t (длины n) и p. А также перестановка a длины n индексов по которой будут удалять символы строки t. Сначала удалят t[a[0]], затем t[a[1]] и тд. Надо найти максимальное число удалений (которые описаны выше), после которых из t можно получить p удалением (уже произвольным способом) некоторых символов из t.

Решение

Сделаем бинпоиск по ответу. Для фиксированного числа удалений, получим строку t. Далее проверим двумя указателями что из текущей строки можно получить p.

Асимптотика $O (n lo g n)$ .

is-algo

игра на строке

Условие

Решение