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.