TAP2015I  Invading aliens
[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wpcontent/uploads/2015/09/pruebaTAP2015.pdf ]
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 ≤ NK such that a_{i+k} = b_{j+k} for k = 1, ..., K up to a permutation of the alphabet.
Input
There are multiple test cases in the input file. For each test case, 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
For each test case, 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.
Example
Input: 3 abc xyz 3 aab cdd 4 abab xyzw 4 xyzw abab 18 imzbyqlgjwrvfspthe rubihyvjnomqdznhat Output: 3 3 2 2 16
hide comments
[Rampage] Blue.Mary:
20160107 05:07:06
I've added many constant optimization to get AC. The time complexity of desired solution is O(n^2), but even this solution with a little bit large constant will get TLE. 

facug91:
20151117 01:26:37
The same solution I've used in BOCA, it's now giving me TLE here. Even that I've optimized it. Could be something wrong with the uploaded file? Thanks in advance! 
Added by:  Fidel Schaposnik 
Date:  20151028 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Argentinian Programming Tournament 2015 