Расскажу авторское решение этой задачи.
Решение методом динамического программирования: состояние - это пара (pos, pref), где pos - позиция в набираемой нами строке-ответе (т.е. от 0 до n), а pref - текущий набранный префикс образца P (т.е. это число от 0 до length(P)). Значение pref будет помогать нам контролировать вхождения образца P: если pref = length(P), то это означает, что в этом месте оканчивается очередное вхождение образца P (а начиналось это вхождение в позиции pos - length(P)).
Значение динамики равно true, если это состояние достижимо. Мы стартуем из состояния (0, 0) и хотим прийти в состояние с pos = n.
При этом в самой динамике мы делаем такие переходы: мы перебираем очередной приписываемый к ответу символ C, и переходим в состояние (pos + 1, newpref), где newpref - это новая подсчитанная длина набранного префикса. Ограничения позволяли пересчитывать это значение newpref втупую, т.е. просто ища в строке P подстроки вида P[length(P) - oldpref..length(P)] + C.
Например, если P = ab, и pref = 1, то при переходе по C = a мы перейдём в newpref = 1 (т.к. к строке a приписали букву a - и получилась aa, но у неё наидлиннейший суффикс, совпадающий с префиксом P, равен a. А вот при переходе по букве C = b мы перейдём в состояние newpref = 2. При переходе по любой другой букве мы перейдём в состояние newpref = 0.
Но на самом деле, конечно, здесь угадывается алгоритм префикс-функции: мы фактически отвечаем на запрос "у нас был набран какой-то префикс образца P, и к нему добавили один символ C - какой будет новый префикс"? На такие запросы как раз и отвечает префикс-функция, и более того, ответы на все такие запросы (запрос - это пара (pref, C)) можно посчитать заранее и брать из таблички (это называется автоматом по префикс-функции).
Так или иначе, если мы смогли посчитать значение newpref, то дальше всё становится просто: мы умеем делать переходы в динамике, потом нужно будет только восстановить по динамике ответ.
Если искать newpref самым кошерным способом - с помощью автомата по префикс-функции, то решение получается за асимптотику O(kn2), но, повторюсь, в задаче проходили решения и с худшими асимпотиками (чтобы не усложнять эту задачу чрезмерно).
P.S. Эта задача интересна тем, что по ней можно придумать всякие нечёткие решения, которые наверняка прошли у участников этого контеста. Одно из таких простых решений, которое не удалось завалить даже спустя пару суток стресса, я напишу чуть позже в комментах.
Решение методом динамического программирования: состояние - это пара (pos, pref), где pos - позиция в набираемой нами строке-ответе (т.е. от 0 до n), а pref - текущий набранный префикс образца P (т.е. это число от 0 до length(P)). Значение pref будет помогать нам контролировать вхождения образца P: если pref = length(P), то это означает, что в этом месте оканчивается очередное вхождение образца P (а начиналось это вхождение в позиции pos - length(P)).
Значение динамики равно true, если это состояние достижимо. Мы стартуем из состояния (0, 0) и хотим прийти в состояние с pos = n.
При этом в самой динамике мы делаем такие переходы: мы перебираем очередной приписываемый к ответу символ C, и переходим в состояние (pos + 1, newpref), где newpref - это новая подсчитанная длина набранного префикса. Ограничения позволяли пересчитывать это значение newpref втупую, т.е. просто ища в строке P подстроки вида P[length(P) - oldpref..length(P)] + C.
Например, если P = ab, и pref = 1, то при переходе по C = a мы перейдём в newpref = 1 (т.к. к строке a приписали букву a - и получилась aa, но у неё наидлиннейший суффикс, совпадающий с префиксом P, равен a. А вот при переходе по букве C = b мы перейдём в состояние newpref = 2. При переходе по любой другой букве мы перейдём в состояние newpref = 0.
Но на самом деле, конечно, здесь угадывается алгоритм префикс-функции: мы фактически отвечаем на запрос "у нас был набран какой-то префикс образца P, и к нему добавили один символ C - какой будет новый префикс"? На такие запросы как раз и отвечает префикс-функция, и более того, ответы на все такие запросы (запрос - это пара (pref, C)) можно посчитать заранее и брать из таблички (это называется автоматом по префикс-функции).
Так или иначе, если мы смогли посчитать значение newpref, то дальше всё становится просто: мы умеем делать переходы в динамике, потом нужно будет только восстановить по динамике ответ.
Если искать newpref самым кошерным способом - с помощью автомата по префикс-функции, то решение получается за асимптотику O(kn2), но, повторюсь, в задаче проходили решения и с худшими асимпотиками (чтобы не усложнять эту задачу чрезмерно).
P.S. Эта задача интересна тем, что по ней можно придумать всякие нечёткие решения, которые наверняка прошли у участников этого контеста. Одно из таких простых решений, которое не удалось завалить даже спустя пару суток стресса, я напишу чуть позже в комментах.
Ну вот у нас есть за O(n), но только это нечёткое решение, которое я анонсировал :)
Решение такое: ну, понятно, поприкладывать паттерн P там, где стоят единички. Дальше надо чем-то заполнить оставшиеся позиции. Вот, и утверждается, заполнять надо любой буквой, отличной от P[preffunc[length(P) - 1]], т.е. любую букву, отличную от той, которая идёт после длиннейшего префикс-суффикс совпадения.
Например, P = "aba". Тогда заполнять пустоты можно любой буквой, отличной от "b".
Почему это - я долго пытался доказать или опровергнуть, но моего владения префикс-функцией оказалось недостаточно :) Стресс, как я уже говорил, тоже не смог обломать это решение.
Оставшиеся позиции, можно было заполнять перебором с отсечениями. перебор от 2х параметров pos и маски тех позиций, начиная с которых образец не должен встречаться (нолики из битовой маски из входных данных), и которые ище небыли удовлетворены. Понятие "удовлетвореная позиция" означает то, что мы уже ранее поставили какой-то символ таким образом, что вхождение образца уже гарантировано не будет в этой позиции.
Ссылку на это свое решение стыдно кидать по многим причинам, но кому уж очень интересно смогут найти сами :-[
please put this to english in your blog
thanks , very nice problem's ....
На дорешивании сдал следующее решение - накладываем образец на строку там где указано, потом пытаемся заполнить пробелы - последовательно от начало до конца ставим символ в очередное свободное место, такой, чтобы значение префикс-функции в этой позиции было минимальным.
Ну фактически дальше, после того как мы посчитали все такие переходы, мы делаем обход в ширину: стартуем из (pos=0, pref=0), и хотим прийти в (pos=N).
Как мы учитываем маску? Мы каждый раз при выполнении перехода смотрим на получающееся значение pref: если оно равно length(P), то надо, чтобы в маске pos-length(P)-ый бит был равен '1', а иначе - он должен быть равен '0'. Если это условие не прошло - то соответствующий переход в динамике (или обходе в ширину, как угодно это называть) запрещаем, иначе разрешаем.