can someone explain how this solution is formed http://www.codechef.com/viewplaintext/2279326 for A6 Problem - CodeChef problem

Thue-Morse sequence.

Let X be Thue-Morse sequence with length which is a power of 2 and greater than the pattern length.

X’ be flipped X.

All prefixes must lie in :

X,

XX’,

XX’X’X,

XX’X’XX’XXX’

Next the problem can be solved using Z Algorithm