By AdHocMan, 13 months ago,

Today I was trying to solve the problem CF R1600 — Camp Schedule. I realized that I will need the longest prefix of a string which is also a suffix of that string. I searched it on google and found that it is called 'Prefix Function'. I tried to understand this concept from the CP Algorithms article, but I am too dumb to understand it.

Though I got the code from there what I needed, I can't understand how it works. Can anyone please help me to understand this concept? (with some examples?)

Prefix Function Code

Note: I am very new to this type of algorithms.

• +14

 » 13 months ago, # |   +1 Go to youtube and type "tushar roy kmp algorithm"
 » 13 months ago, # |   +5 Lets get the basic things clear. $\pi[i] - \pi[i-1] \le 1$, because each new character, can add only one more match.In my amazing drawing, The substrings covered by the same color are the same, and we have processed upto $i$. First we check, if we can extend red. That requires $C_2 = C_3$. If that is not true, we need to check with the next lower match. The next lower match, is cyan. to check if cyan works, we have to check $C_1 = C_3$. Now if cyan doesnt work either, we want such a matching inside cyan. Which is $\pi[\pi[\pi[i]]]$. And we continuously keep on going down, to the next largest, until the next character matches. This is $O(n)$, because checking characters takes $O(1)$. Each character can add most one to $\pi$. and each, time we go back, the matching decreases by at least $1$. So we can deduce that the number of times the while loop runs cannot be more than $O(n)$.Also keep in mind, is that the substrings may intersect, but it doesn't really matter. I didnt draw intersecting substrings, to not make the diagram too messy.
•  » » 13 months ago, # ^ |   +1 while(j > 0 && s[j] != s[i]) j = pi[j - 1];Isn't this that part which is searching the next lower match?
•  » » » 13 months ago, # ^ |   +2 Well, read the loop like this. while there is some matching left before it if Characters at the positions are equal : break else : go to next smaller matching. 
•  » » » » 13 months ago, # ^ |   +1 Thank you so much. The explanation was very clear to understand.
 » 6 weeks ago, # | ← Rev. 2 →   0 check this out: https://www.youtube.com/watch?v=KG44VoDtsAA&t=175s the video link is to Tushar Roy's channel, where he has explained the prefix_array formation.just 2 make your life easier: here I post my python code for the prefix array formation. keep in mind: prefix_array formation is the same as KMP, but KMP on itself...that means both the text and the pattern is the same. def prefix_array(s): i = 1;j = 0; pa = [0]*len(s); # this is a static array of length as same as length of string 's' and initialised # with value 0 while(i < len(s)): if(s[i] == s[j]): pa[i] = j+1; i = i+1; j = j+1; else: if(j != 0): j = pa[j-1]; else: i = i+1; return pa; print(prefix_array("aabaaab"));