I'll describe here an author's solution for this problem.
The solution is by a method of dynamic programming: the state is a pair (pos, pref), where pos - the position in the string built (it is between 0 and n), and pref - the current prefix of pattern P (i.e. this is a number between 0 and length(P)). The value pref will help us to control all occurences of pattern P: if pref = length(P) then it means that here is an ending of occurence of pattern P (the beginning of the occurence was at pos - length(P)).
The value D[pos][pref] of the dynamic is true, if the state is reachable. We start from the state (0, 0) and want to get to any state with pos = n.
How to make moves in the dynamic? We iterate over all possible characters C and try to add it to the current answer. That's why we get into a stage (pos + 1, newpref), where newpref is a new length of prefix of P. The problem constraints permitted to calculate this value newpref easily, i.e. just by searching for substrings of form P[length(P) - oldpref..length(P)] + C in the pattern P.
For example, if P = ab and pref = 1, then with the character C = a we will get into newpref = 1 (because we added character a to the string a, - we got string aa, but its longest suffix matching with the prefix of string P equals to a). If we took C = b then we would get into state newpref = 2. Any other character would move us into the state with newprefix = 0.
But in reality, of course, an algorithm for calculating prefix-function can be guessed here. Really, in fact, we answer the following query: "we had some prefix of pattern P and added character C by its end - so what will be the new prefix?". These queries are answered exactly by prefix-function algorithm. Moreover, we can pre-calculate answers to all of these queries in some table and get answers for them in O(1) from the table. This is called an automaton built over the prefix-function.
One way or another, if we've taught how to calculate newpref, then everything is quite simple: we know how to make movements in dynamics from one state to another. After getting the solution we'll have just to restore the answer-string itself.
The solution's asymptotics depends on the way we chose to calculate newpref. The fastest way is using the prefix-function automaton, and the asymptotics in this case is O(kn2). But, I remind, the problem's constraints allowed to choose some simpler way with worse asymptotics.
P.S. This problem was additionally interesting by the fact that one can invent many strange simple solutions, which are very difficult to prove (and most of them will have counter-examples, but very rare ones). Some of these tricky solutions passed all systests in the round. I have also created one relatively simple solution that looks rather unlike to be right, but we didn't manage to create counter-example even after several hours of stress :)
The solution is by a method of dynamic programming: the state is a pair (pos, pref), where pos - the position in the string built (it is between 0 and n), and pref - the current prefix of pattern P (i.e. this is a number between 0 and length(P)). The value pref will help us to control all occurences of pattern P: if pref = length(P) then it means that here is an ending of occurence of pattern P (the beginning of the occurence was at pos - length(P)).
The value D[pos][pref] of the dynamic is true, if the state is reachable. We start from the state (0, 0) and want to get to any state with pos = n.
How to make moves in the dynamic? We iterate over all possible characters C and try to add it to the current answer. That's why we get into a stage (pos + 1, newpref), where newpref is a new length of prefix of P. The problem constraints permitted to calculate this value newpref easily, i.e. just by searching for substrings of form P[length(P) - oldpref..length(P)] + C in the pattern P.
For example, if P = ab and pref = 1, then with the character C = a we will get into newpref = 1 (because we added character a to the string a, - we got string aa, but its longest suffix matching with the prefix of string P equals to a). If we took C = b then we would get into state newpref = 2. Any other character would move us into the state with newprefix = 0.
But in reality, of course, an algorithm for calculating prefix-function can be guessed here. Really, in fact, we answer the following query: "we had some prefix of pattern P and added character C by its end - so what will be the new prefix?". These queries are answered exactly by prefix-function algorithm. Moreover, we can pre-calculate answers to all of these queries in some table and get answers for them in O(1) from the table. This is called an automaton built over the prefix-function.
One way or another, if we've taught how to calculate newpref, then everything is quite simple: we know how to make movements in dynamics from one state to another. After getting the solution we'll have just to restore the answer-string itself.
The solution's asymptotics depends on the way we chose to calculate newpref. The fastest way is using the prefix-function automaton, and the asymptotics in this case is O(kn2). But, I remind, the problem's constraints allowed to choose some simpler way with worse asymptotics.
P.S. This problem was additionally interesting by the fact that one can invent many strange simple solutions, which are very difficult to prove (and most of them will have counter-examples, but very rare ones). Some of these tricky solutions passed all systests in the round. I have also created one relatively simple solution that looks rather unlike to be right, but we didn't manage to create counter-example even after several hours of stress :)
please put this to english in your blog
thanks , very nice problem's ....