AdHocMan's blog

Help needed in understanding the prefix function.
By AdHocMan, 4 years ago, In English

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.

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Go to youtube and type "tushar roy kmp algorithm"

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    while(j > 0 && s[j] != s[i]) j = pi[j - 1];

    Isn't this that part which is searching the next lower match?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank you so much. The explanation was very clear to understand.

        → Reply