La práctica de esteganografía
La esteganografía (del griego steganos, cubierto u oculto, y graphos, escritura) estudia técnicas que permitan ocultar mensajes dentro de otros (llamados portadores) de modo que no se perciba la presencia de los primeros. Es decir, procura ocultar mensajes dentro de otros de modo que el propio acto de la comunicación pase inadvertido para un probable intruso, que ni siquiera sabrá que se está transmitiendo información sensible.
En la escuela de esteganografía de Atenas, a Ocultaniakis le han puesto una práctica: tiene que encontrar la forma de esconder un número en un mensaje. Lo primero que se le ha ocurrido es introducirlo en una lista larga de números, pero le parece que esta solución es muy sencilla y recibirá poca nota en su evaluación. Así que ha decidido dar una vuelta de tuerca más a la esteganografía y hacer que el número oculto no esté presente en el mensaje, sino que haya que calcularlo buscando una clave oculta en el mismo.
La clave estará formada por una serie corta de números distintos. Estos aparecerán, posiblemente varias veces, dentro de una lista larga de números, el mensaje completo. El número secreto será la longitud de la subsecuencia más corta del mensaje que contenga los números de la clave en el mismo orden. En concreto, si la clave son los números c1, c2, … , cr, y el mensaje m1, m2, … , mn, una subsecuencia del mensaje contiene la clave si existen índices 1 ≤ i1 < … < ir ≤ n, tales que \(m_{i_1} = c_1, \ldots, m_{i_r} = c_r\). Y en ese caso la longitud de la subsecuencia es ir − i1 + 1.
¿Sabrías recuperar la información escondida en un mensaje generado por Ocultaniakis?
Entrada
La entrada estará formada por una serie de casos de prueba. Cada caso está formado por 3 líneas: la primera contiene el tamaño R de la clave, entre 2 y 10 números y el tamaño N del mensaje, entre R y 250.000; la segunda contiene los R números de la clave, todos distintos, en el orden en el que deben aparecer en el mensaje; y la tercera contiene los N números del mensaje.
Se garantiza que la clave siempre aparece al menos una vez oculta en el mensaje. Los números que aparecen tanto en la clave como en el mensaje están entre 1 y 10.000.
Salida
Para cada caso de prueba se escribirá una línea que contenga la longitud (número de elementos) de la subsecuencia más corta del mensaje que contenga la clave.
Entrada de ejemplo
3 10 1 2 3 5 1 3 2 1 7 3 2 3 8 2 4 3 1 31 3 5 1
Salida de ejemplo
5 3