If more than one periodic permutation could have mapped the plain text to the cyphertext1, then apply the periodic permutation that has the smallest value for k. There will never be more than one shortest permutation function that matches the data.
In your example the smallest value for k is 8, but there are many permutation functions that match the data. According to the problem description, there will be no such cases in the input! (This implies that we need no ambiguity checks, which makes the program easier.)
Consider this example:
Here we can find permutation functions with lengths 4,8 and 16. Testing length 4:
- the permutation "aaaa" -> "aaaa" leaves all possible functions valid (1234, 1243, 1324, etc, total of 24);
- the permutation "bbcc" -> "ccbb" limits us to 4 functions (3412, 3421, 4312 and 4321);
- the permutation "uvwx" -> "xwuv" gives only one function: 4312,
- the last permutation is the same as the third.
The answer is unique: 4312, and is compatible with all permutations found.
Here the first three permutations are the same as in the example above. But the fourth is not; the only valid function for "klmn" -> "nmlk" is 4321, which is not compatible with the first three. Therefore k=4 has no valid function.
Now we test length 8, and by the same reasoning we find one unique function 43128765, which is the answer.
Sorry for this lengthy reply, but I hope it clears matters.
junbin's examples are, as far as I checked them, for the most part highly ambiguous and therefore invalid (apart from wasting space on the board). I'd sugest he removes them.