3389 - Invading Aliens 3389 - Invasión Extraterrestre 3389 - Invading Aliens

Statistics Sub: 101 | AC: 24 | AC%: 23,76 | Score: 3,33
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Fidel I. Schaposnik
Added by fidels (2015-10-12)
Limits
Total Time: 5000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

In the novel "A for Andromeda", by Fred Hoyle and John Elliot, a civilization from a planet in orbit around a star in the constellation of Andromeda, 200 light years away from our Solar System, decides to colonize the galaxy. To avoid the long and costly interstellar travels, this civilization decides to perform the colonization at a distance, by sending a signal instead of ships (this signal contains instructions on how to build a supercomputer with an artificial intelligence capable of taking over the world of the unfortunate civilizations who build it, but that is not our problem for the moment).

One of the issues humans have to overcome in order to construct the supercomputer is the decoding of the signal. As it happens, the aliens send two messages in two different frequencies, repeating endlessly in each of them a code with N characters. For example, if N = 3 and one of the codes is "abc", the alien message in the corresponding frequency will be "...cabcabcabcab...", where the ellipsis mean that the code is repeated infinitely both backwards and forwards. For this reason, the terrestrial stations receiving the signal are incapable of telling what the emitted code actually is, as there can be more than one code that is compatible with a given message. In our example, knowing that N = 3 they could interpret that the code is any of three possibilities "abc", "bca" and "cab".

Complicating matters even further, although both messages are composed solely of characters from the alphabet 'a' through 'z', because they are transmitted in different frequencies there exists an ambiguity in the identification of the characters between them. Thus, if we let the characters be named c[1] = 'a', c[2] = 'b', and so on until c[26] = 'z', it is possible that every occurrence of the character c[i] in one of the messages is replaced by the character c[σ(i)] in the other message, where σ(i) is an arbitrary permutation of the numbers from 1 to 26. For instance, if we have σ(1) = 24, σ(2) = 25 and σ(3) = 26 the code "abc" in one of the frequencies will be turned in the other into "xyz", so that the corresponding message will be "...zxyzxyzxyzxy...".

You've been put in charge of decoding the alien signal, and your task is to determine the maximum length of a common substring that two codes compatible with the received messages can have. This is, you should find the maximum value K such that one of the messages is compatible with the code a[1] a[2] ... a[N] and the other is compatible with the code b[1] b[2] ... b[N], and there exist i and j with 0 <= i, j <= N-K such that a[i+k] = b[j+k] for k = 1, ..., K up to a permutation of the alphabet.
En la novela "A for Andromeda" de Fred Hoyle y John Elliot, una civilización que habita un planeta en órbita alrededor de una estrella de la constelación de Andromeda, a 200 años luz del sistema solar, decide colonizar la galaxia. Para evitar los largos y costosos viajes interestelares, esta civilización decide realizar la colonización a distancia, enviando una señal en lugar de naves (dicha señal contiene instrucciones para armar una supercomputadora con una inteligencia artificial capaz de apoderarse del mundo de las desdichadas civilizaciones que la construyan, pero ese no es nuestro problema por el momento).

Uno de los inconvenientes que los humanos deben sortear para construir la supercomputadora es la decodificación de la señal. Ocurre que los alienígenas emiten dos mensajes en dos frecuencias distintas, repitiendo en cada una de ellas un código de N caracteres en un bucle infinito. Por ejemplo, si N = 3 y uno de los códigos es "abc", el mensaje alienígena en la frecuencia correspondiente será "...cabcabcabcab...", donde los puntos suspensivos indican que el código se repite infinitamente tanto hacia atrás como hacia adelante. Por esta razón, las estaciones terrestres que reciben la señal no son capaces de determinar cuál es realmente el código emitido, ya que puede haber más de un código compatible con un dado mensaje. En el ejemplo anterior, sabiendo que N = 3 podrían interpretar que el código es cualquiera de las tres posibilidades "abc", "bca" y "cab".

Para complicar aún más las cosas, si bien los dos mensajes recibidos están compuestos solamente por caracteres del alfabeto de la 'a' a la 'z', como son transmitidos en frecuencias distintas existe una ambigüedad en la identificación de los caracteres entre uno y otro. De este modo, si llamamos a los caracteres c[1] = 'a', c[2] = 'b', y así siguiendo hasta c[26] = 'z', es posible que todas las apariciones del caracter c[i] en uno de los mensajes sean reemplazadas por el caracter c[s(i)] en el otro, siendo s(i) una permutación arbitraria de los números del 1 al 26. Así, si tenemos por ejemplo s(1) = 24, s(2) = 25 y s(3) = 26, el código "abc" en una frecuencia se transformaría en la otra en "xyz", de manera que el mensaje correspondiente será "...zxyzxyzxyzxy...".

Como encargados de la decodificación de la señal alienígena, su tarea es determinar la longitud de la máxima sub-cadena común que pueden tener dos códigos compatibles con los mensajes recibidos. Esto es, deben determinar el máximo valor de K tal que uno de los mensajes es compatible con el código a[1] a[2] ... a[N] y el otro es compatible con el código b[1] b[2] ... b[N], existiendo además i y j con 0 <= i, j <= N-K tales que, a menos de una permutación del alfabeto, a[i+k] = b[j+k] para k = 1, ..., K.
In the novel "A for Andromeda", by Fred Hoyle and John Elliot, a civilization from a planet in orbit around a star in the constellation of Andromeda, 200 light years away from our Solar System, decides to colonize the galaxy. To avoid the long and costly interstellar travels, this civilization decides to perform the colonization at a distance, by sending a signal instead of ships (this signal contains instructions on how to build a supercomputer with an artificial intelligence capable of taking over the world of the unfortunate civilizations who build it, but that is not our problem for the moment).

One of the issues humans have to overcome in order to construct the supercomputer is the decoding of the signal. As it happens, the aliens send two messages in two different frequencies, repeating endlessly in each of them a code with N characters. For example, if N = 3 and one of the codes is "abc", the alien message in the corresponding frequency will be "...cabcabcabcab...", where the ellipsis mean that the code is repeated infinitely both backwards and forwards. For this reason, the terrestrial stations receiving the signal are incapable of telling what the emitted code actually is, as there can be more than one code that is compatible with a given message. In our example, knowing that N = 3 they could interpret that the code is any of three possibilities "abc", "bca" and "cab".

Complicating matters even further, although both messages are composed solely of characters from the alphabet 'a' through 'z', because they are transmitted in different frequencies there exists an ambiguity in the identification of the characters between them. Thus, if we let the characters be named c[1] = 'a', c[2] = 'b', and so on until c[26] = 'z', it is possible that every occurrence of the character c[i] in one of the messages is replaced by the character c[σ(i)] in the other message, where σ(i) is an arbitrary permutation of the numbers from 1 to 26. For instance, if we have σ(1) = 24, σ(2) = 25 and σ(3) = 26 the code "abc" in one of the frequencies will be turned in the other into "xyz", so that the corresponding message will be "...zxyzxyzxyzxy...".

You've been put in charge of decoding the alien signal, and your task is to determine the maximum length of a common substring that two codes compatible with the received messages can have. This is, you should find the maximum value K such that one of the messages is compatible with the code a[1] a[2] ... a[N] and the other is compatible with the code b[1] b[2] ... b[N], and there exist i and j with 0 <= i, j <= N-K such that a[i+k] = b[j+k] for k = 1, ..., K up to a permutation of the alphabet.

Input specification

The first line contains an integer N representing the length of the codes emitted by the aliens (1 <= N <= 1000). Each of the two following lines contains the description of the message received in a different frequency, in the form of a string of N characters from 'a' to 'z'. The received message is obtained repeating endlessly the corresponding string.
La primera línea contiene un entero N que representa la longitud de los códigos emitidos por los alienígenas (1 <= N <= 1000). Cada una de las dos líneas siguientes contiene la descripción del mensaje recibido en una frecuencia distinta, en la forma de una cadena de N caracteres de la 'a' a la 'z'. El mensaje recibido se obtiene repitiendo la cadena correspondiente infinitamente.
The first line contains an integer N representing the length of the codes emitted by the aliens (1 <= N <= 1000). Each of the two following lines contains the description of the message received in a different frequency, in the form of a string of N characters from 'a' to 'z'. The received message is obtained repeating endlessly the corresponding string.

Output specification

Print one line containing an integer representing the maximum length of a common substring two codes which are compatible with the received messages can have.
Imprimir en la salida una línea conteniendo un entero que representa la longitud de la máxima sub-cadena común que pueden tener dos códigos que sean compatibles con los mensajes recibidos.
The first line contains an integer N representing the length of the codes emitted by the aliens (1 <= N <= 1000). Each of the two following lines contains the description of the message received in a different frequency, in the form of a string of N characters from 'a' to 'z'. The received message is obtained repeating endlessly the corresponding string.

Sample input

3
abc
xyz

Sample output

3

Hint(s)

Sample input #2
3
aab
cdd

Sample output #2
3

Sample input #3
4
abab
xyzw

Sample output #3
2

Sample input #4
4
xyzw
abab

Sample output #4
2

Sample input #5
18
imzbyqlgjwrvfspthe
rubihyvjnomqdznhat

Sample output #5
16
Sample input #2
3
aab
cdd

Sample output #2
3

Sample input #3
4
abab
xyzw

Sample output #3
2

Sample input #4
4
xyzw
abab

Sample output #4
2

Sample input #5
18
imzbyqlgjwrvfspthe
rubihyvjnomqdznhat

Sample output #5
16
Sample input #2
3
aab
cdd

Sample output #2
3

Sample input #3
4
abab
xyzw

Sample output #3
2

Sample input #4
4
xyzw
abab

Sample output #4
2

Sample input #5
18
imzbyqlgjwrvfspthe
rubihyvjnomqdznhat

Sample output #5
16

Recommendation

We have carefully selected several similar problems: 3376 | 3380 | 2441 | 3166 | 2534 | 2141