# Unable to understand control flow in KMP algorithm

I am facing problem in understanding the KMP algorithm as given in the book "Introduction to Algorithm" by Cormen et. al. (Chapter 32):  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)

• if and while scope is indicated by indentation. Line 6 while ends at line 7, line 10 if ends at line 12. Mar 24 '13 at 16:09
• No: $\pi$ is strictly decreasing, thus there are at most $k$ iterations of this loop. Oct 19 '13 at 20:05
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.