Как решить эту задачу с КФ ЕДУ? Дайте подсказку как это решить, не могу никак додумать.
Вроде можно так (идейно, если это не работает то @Zhabka задуши)
Пусть b_0, b_1 \ldots b_k = set(p) - то есть множество всех букв в p
Функция 1(s)
Бинпоиском мы найдем позиции в которых лежат b_i в строке s
Типа search(b_0) \to b удаляем элемент с индексом b из массива s и снова ищем
Получим массивы m_0, m_1 \ldots m_k то есть m_i - индексы в которых лежит a_i
Функция 2(m_0, m_1 \ldots m_k)
Сортанем массивы m_i - по неубыванию
Берем 0 \leq i \leq len(p) - 1 будем бегать от 1 до p
Берем min(m_{p[i]}) и выкалываем его потом i \to i+1
Если мы на каждом шаге нашли min(m_{p[i]}) - то есть он оказался не пустым, то такая строка существует
Положим i = 0
Далее мы делаем так: Функция 1 (s) \to Функция 2 (m_0, m_1, \ldots m_k) (если функция 2 сказала что такой строки нет, то ответ это i - 1, break) иначе выкалываем из строки s элемент a[i] и повторяем
2 лайка
Думаю в этом задании подразумевалось решение бинпоиском по ответу.
Пусть мы можем сделат k шагов и после них мы всё ещё можем получить слово p , давайте заметим что если мы можем сделать k шагов то мы можем сделать любое количество шагов x такое что x \leq k. Так что давайте бинарить m, и проверять можем ли мы выполнить m шагов и получить слово p. Если не может то ищем ответ слева от m, иначе справа m.
Как проверять подумай сам, если нужна подсказка напиши сюда.
2 лайка
У Пети есть слово t, он хочет, чтобы из него получилось слово p