Prefix Function+ DP

Revision en1, by Nams, 2016-01-07 17:43:08

Hello all,

I was doing DP problems in Problemset section of Codeforces, when I came across this question involving prefix function :

Problem

I could do this question in O(n^2) using simple search and KMP but as evident constraints are such that the problem needs to be solved in O(n). I went to see the editorial for the problem but I could not get the approach.

Editorial

I know the principle of prefix function and I know how it is calculated but the approach in the editorial just went above my head. So please elaborate the editorial approach. Any new solution is also welcomed.

Thanks in advance.

Tags prefix function, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Nams 2016-01-07 17:43:08 739 Initial revision (published)