SP25480 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 \] 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 , **j such that **a $ _{i+k} $ = b $ _{j+k} $** for **k = 1, ..., K** up to a permutation of the alphabet.****

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 ). 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.**

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.