Now I'm going to give a solution of problem CRYPTO4. Many Thanks to the help of Carlos Eduardo Rodrigues Alves.
Actually, we need to know all possible value of n. We can generate the whole message if and only if the value of n is known. A brute force solution is easy to find: for each n between 1 and m, decide if there's a conflict between the original message and the encoded message. If the answer is no, then generate the whole message. After comparing all the possible messages, you can find all the missing characters that can be determined.
This solution is too tough and actually gets Time Limit Exceeded. My solution is based on that, with these optimizations:
*Keep a list of the positions of the characters (called todo-list) that still have possibility to be fixed(i.e. We know the character on that position in the encoded message but we don't know the one in the original message.)
*Keep a list of the positions of the characters that is already known in both message. The conflict will occur on these characters.
*Obviously, if the messages are valid when n equals to some value x, then it must be valid when n equals to any multiple of x. So we only need to check all the values between m/2+1 and m(inclusive).
*Assume that now we are check if n = x is valid. The conflict will NOT occur before the x-th character.
*Once a character in some position can not be fixed, delete it from the todo-list.
These optimizations make the program terminate within the 17 second time limit.
P.S. After about 10 submissions in contest SPOJPL, I realized that there is only one test case which satisfies that m is about 100000 and the length of the message is about 1000000. So perhaps the solution above is fast only to this test case, but who knows...