Unable to understand control flow in KMP algorithm

Question

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

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

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.
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?
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. — adrianN, Commented Mar 24, 2013 at 16:09
Please transcribe the algorithms instead of posting pictures. — Raphael, Commented Mar 25, 2013 at 10:12
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. — Radu, Commented Oct 19, 2013 at 19:35
No: $\pi$ is strictly decreasing, thus there are at most $k$ iterations of this loop. — frafl, Commented Oct 19, 2013 at 20:05

Karolis Juodelė · Accepted Answer · 2013-03-25 19:59:06Z

2

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.
Indeed it only matters whether q and k are not zero.

answered Mar 25, 2013 at 19:59

Karolis Juodelė

3,68715 silver badges18 bronze badges

Add a comment |

1 Answer 1