Module: Función de prefijo, función Z


Problem

10 /10


Cifrar

Theory Click to read/hide

 
Tanto Z como el prefijo de función se pueden usar para implementar el algoritmo KMP(Knuth-Morris-Pratt) para encontrar una subcadena en una cadena en O(|S|). La esencia de este algoritmo es la siguiente: atribuimos a la cadena que queremos encontrar la cadena en la que estamos buscando. Es muy recomendable poner un carácter separador entre estas líneas, es decir, un carácter que no aparece en ninguna línea (generalmente #).

Problem

Corwin pudo interceptar n mensajes sobre los movimientos de tropas de Eric. Es cierto que resultaron estar encriptados, ¡pero no importa! ¿Le ayudarás a descifrar estos mensajes? Esto no debería ser difícil, ya que Corwin conoce al menos una subcadena en cada mensaje original.

Para el cifrado, se sabe que Eric usa un cifrado César, es decir, un cifrado en el que la letra con el número i se reemplaza por la letra con el número i + k , donde k es un número.

Dado que los compiladores modernos no son compatibles con el alfabeto ámbar, reemplazaremos los caracteres con su número de serie: un número del 1 a q, donde < code> q - el número de caracteres en el alfabeto.

Cada mensaje tiene una longitud de x, y cada subcadena conocida de su descifrado es y.

Su objetivo es restaurar todos los mensajes originales.

¡¡EL PROVEEDOR CON STD::STRING irá a los patios del CAOS!!!
 
Entrada
La primera línea lee números n (\(1 <= n <= 100\)) y q < /código> (\(1 <= k <= 100\))
Las siguientes líneas 3 * n contienen números xi, yi (\(1 <= b_i <= a_i <= 100\)) y 2 matrices de números que representan el mensaje y su subcadena de descifrado.

Impresión
En el número de línea i imprima la versión decodificada del mensaje con el número i.
Debe haber NO DEBE al final de esta línea


Ejemplos

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!

# Entrada Salida
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