1
$\begingroup$

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)

$\endgroup$
  • 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 '13 at 16:09
  • 2
    $\begingroup$ Please transcribe the algorithms instead of posting pictures. $\endgroup$ – Raphael Mar 25 '13 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 '13 at 19:35
  • $\begingroup$ No: $\pi$ is strictly decreasing, thus there are at most $k$ iterations of this loop. $\endgroup$ – frafl Oct 19 '13 at 20:05
2
$\begingroup$
  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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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