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 (

The value

How to make moves in the dynamic? We iterate over all possible characters

For example, if

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

One way or another, if we've taught how to calculate

The solution's asymptotics depends on the way we chose to calculate

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*(*kn*^{2}) . 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 ....