И Z, и префикс функции могут использоваться для реализации алгоритма КМП(Кнута-Морриса-Пратта), предназначенного для поиска подстроки в строке за O(|S|). Суть этого алгоритма такова: приписываем к строке, которую мы хотим найти, строку, в которой ведется поиск. Очень желательно между этими строками поставить разделительный символ, т. е. символ, который не встречается ни в одной строке (обычно #).
Задача
Корвину удалось перехватить n
сообщений о перемещении войск Эрика. Правда, они оказались зашифрованными, но это не беда! Вы ведь поможете ему расшифровать эти сообщения? Это должно быть не сложно, ибо Корвин знает хотя бы одну подстроку в каждом исходном сообщении.
Известно, что для шифровки Эрик использует шифр Цезаря, то есть шифр, в котором буква с номером i
заменяется на букву с номером i + k
, где k
- некоторое число.
Так как современные компиляторы не поддерживают амберский алфавит, мы будем заменять символы на их порядковый номер - число от 1
до q
, где q
- количество символов в алфавите.
Каждое сообщение имеет длину x
, а каждая известная подстрока его расшифровки - y
.
Ваша цель - восстановить все изначальные сообщения.
СДАВШИЙ С ПОМОЩЬЮ STD::STRING ОТПРАВИТСЯ ВО ДВОРЫ ХАОСА!!!
Входные данные
В первой строке считываются числа n
(\(1 <= n <= 100\)) и q
(\(1 <= k <= 100\))
В следующих 3 * n
строках содержатся числа xi
, yi
(\(1 <= b_i <= a_i <= 100\)) и 2 массива с числами, являющиеся сообщением и его подстрокой его расшифровки.
Выходные данные
В строке номер
i
выведите расшифрованный вариант сообщения с номером
i
.
В конце этой строки пробела быть
НЕ ДОЛЖНО
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1 11
10 4
11 7 1 1 2 6 7 1 1 8
2 7 7 8 |
6 2 7 7 8 1 2 7 7 3 |