amanjain1108935's blog

Some More Homework
By amanjain1108935, 11 years ago, In English

Can someone explain how to go through this problem http://www.codechef.com/problems/A6. I have found this solution but i can't understand its precomputation part. http://www.codechef.com/viewplaintext/2279326

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply