I am facing problem in understanding the KMP algorithm as given in the book "Introduction to Algorithm" by Cormen et. al. (Chapter 32):

enter image description here

enter image description here

With respect to the above algorithm, I have following question:

  1. In both the algorithms, where exactly (which line number?) while loops, if and for loop ends? It is difficult to visualize the functioning of the algorithm without knowing the 'end' for each loop and conditional statements.

  2. On line number 6 in KMP-MATCHER() and COMPUTE-PREFIX-FUNCTION(), what is the need of checking q>0 and k>0, when we know q and k will always be 0 or positive. Or do the authors want to test q!=0, k!=0?

  3. If q=0 and i=1 in KMP-MATCHER(), from 6 to 10 which line will be executed (If I get answer to 1- above then I can find this)

  • 2
    $\begingroup$ if and while scope is indicated by indentation. Line 6 while ends at line 7, line 10 if ends at line 12. $\endgroup$
    – adrianN
    Mar 24, 2013 at 16:09
  • 2
    $\begingroup$ Please transcribe the algorithms instead of posting pictures. $\endgroup$
    – Raphael
    Mar 25, 2013 at 10:12
  • $\begingroup$ I also have the impression that the algorithm is wrong, for instance for a string of the form "bba" the "COMPUTE-PREFIX-FUNCTION" will loop infinitely on lines 6-7 in the second step of the for. $\endgroup$
    – Radu
    Oct 19, 2013 at 19:35
  • $\begingroup$ No: $\pi$ is strictly decreasing, thus there are at most $k$ iterations of this loop. $\endgroup$
    – frafl
    Oct 19, 2013 at 20:05

1 Answer 1

  1. As explained in the comments, indentation marks code blocks. It is a standard way to denote them. while of line 6, repeats line 7, but has nothing to do with the if on line 8.

  2. Indeed it only matters whether q and k are not zero.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.