Module: Função de prefixo, função Z


Problem

10 /10


Cifra

Theory Click to read/hide

 
Tanto Z quanto o prefixo da função podem ser usados ​​para implementar o algoritmo KMP(Knuth-Morris-Pratt) para encontrar uma substring em uma string em O(|S|). A essência desse algoritmo é a seguinte: atribuímos à string que queremos encontrar a string na qual estamos pesquisando. É altamente desejável colocar um caractere separador entre essas linhas, ou seja, um caractere que não ocorra em nenhuma linha (geralmente #).

Problem

Corwin foi capaz de interceptar n mensagens sobre os movimentos das tropas de Eric. É verdade que eles estavam criptografados, mas não importa! Você vai ajudá-lo a decifrar essas mensagens? Isso não deve ser difícil, pois Corwin conhece pelo menos uma substring em cada mensagem original.

Para criptografia, Eric é conhecido por usar uma cifra de César, ou seja, uma cifra na qual a letra com o número i é substituída pela letra com o número i + k , onde k é algum número.

Como os compiladores modernos não suportam o alfabeto Amber, substituiremos os caracteres por seus números de série - um número de 1 a q, onde < code> q - o número de caracteres no alfabeto.

Cada mensagem tem x de comprimento, e cada substring conhecida de sua descriptografia é y.

Seu objetivo é restaurar todas as mensagens originais.

O FORNECEDOR COM STD::STRING VAI PARA O JARDIM DO CAOS!!!
 
Entrada
A primeira linha lê os números n (\(1 <= n <= 100\)) e q < /código> (\(1 <= k <= 100\))
As seguintes 3 * n linhas contêm números xi, yi (\(1 <= b_i <= a_i <= 100\)) e 2 matrizes de números que representam a mensagem e sua substring de descriptografia.

Impressão
No número da linha i imprima a versão decodificada da mensagem com o número i.
Deve haver NÃO DEVE no final desta linha


Exemplos
# Entrada Saída
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

time 250 ms
memory 16 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!