Префикс-функция, Z-функция




№ 10/10 Cipher

Read Theory

 
И Z, и префикс функции могут использоваться для реализации алгоритма КМП(Кнута-Морриса-Пратта), предназначенного для поиска подстроки в строке за O(|S|). Суть этого алгоритма такова: приписываем к строке, которую мы хотим найти, строку, в которой ведется поиск. Очень желательно между этими строками поставить разделительный символ, т. е. символ, который не встречается ни в одной строке (обычно #).

Task
Time limit: 250 ms,
Memory limit: 16 Mb

Корвину удалось перехватить 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 <= bi <= ai <= 100) и 2 массива с числами, являющиеся сообщением и его подстрокой его расшифровки.

Выходные данные

В строке номер i выведите расшифрованный вариант сообщения с номером i.
В конце этой строки пробела быть НЕ ДОЛЖНО

Пример
Ввод
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

(c) Евгений Григорьев

Auto CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!
Attach the program source file:
or enter the source code in the language:

Rules for designing programs and a list of errors during automatic task verification
           

Results:
©2009 - 2019 SilverTests.ru/en

Education

Quizes
Problems
Courses

My Account

Register
Sign

About us

Contacts
Rules