KMP String Matching Algorithm stuck in a loop

Question

I'm trying to implement KMP String Matching Algorithm using CLRS, but with the text input as "bbaa" and pattern input as "aab", it gets stuck in an infinite loop in the while loop inside the getKMPPrefix function. My code is given below:

private int[] getKMPPrefix(char[] p, int m) {
    int[] prefix = new int[m];
    prefix[0] = 0;
    int k = 0;
    for(int q = 1; q < m; q++) {
        while(k > 0 && p[k] != p[q] ) { //Stuck here
            k = prefix[k];
        }
        if(p[k] == p[q]) {
            k++;
        }
        prefix[q] = k;
    }
    return prefix;
}

public void kmp(String text, String pattern) {
    char[] t = text.toCharArray();
    char[] p = pattern.toCharArray();
    int n = text.length();
    int m = pattern.length();

    int[] prefix = getKMPPrefix(p, m);

    int q = 0;
    for(int i = 1; i < n; i++) {
        while(q > 0 && p[q] != t[i]) {
            q = prefix[q];
        }
        if(p[q] == t[i]) {
            q++;
        }
        if(q == m) {
            System.out.println("Pattern occurs with shift " + (i-m+1));
            q = prefix[m-1];
        }
    }
}

Any idea why this is the case?

Polynomial Proton · Accepted Answer · 2015-02-02 03:52:19Z

Here is what is happening:

It reaches the line :

while(k > 0 && p[k] != p[q] ) { //Stuck here

k=0 so obviously this will fail and it will jump out of the loop and goto next one

if(p[k] == p[q]) {
            k++;
        }

In you case, the input is aab so this is true p[0]=p[1]=a

Now, k=1

Now you assign k's value to prefix

prefix[q] = k;

Now it runs into deadlock.

It'll go back to while loop now

 while(k > 0 && p[k] != p[q] ) { //Stuck here
            k = prefix[k];
        }

Notice, you just assigned in earlier loop prefix[q] = k; i.e p[1] = 1

when it comes to while loop k=1 and 'p[1] != p[2]' i.e a!=b It passes and goes inside loop

k = prefix[k];

k=1 and prefix[1] = 1, which mean you are reassigning the value 1 to k

It goes back again to while loop and value of k=1 and p=1 since it never went past the while loop to increment p

There is the deadlock, the condition will remain true for the while loop and the program will never come out of while loop.

Either you can change you while loops condition or increment p inside while loop or break inside while after certain condition. I explained the Deadlock, try and figure out the program yourself though. Goodluck

JustVirtually · Accepted Answer · 2015-11-17 06:54:35Z

private static int[] computPrefix(String P) 
    {
        int m = P.length();
        int[] prefix = new int[m];
        prefix[0]=0; // you just mentioned this
        prefix[1]=0; // mention this in initial condition
        int k = 0;
 // start loop form i = 2. You can find the clear explanation in CLRS page number 1002
        for(int i = 2; i<m; i++)
        {
            while(k>0 && P.charAt(k) != P.charAt(i))
            {
                k = prefix[k]; // NO deadlock
            }

            if(P.charAt(k)==P.charAt(i))
            {
                k++;
            }
            prefix[i] = k;
        }
        return prefix;
    }

You code will cause deadlock for example if pattern is "aabaaa". This correct condition will generate prefix in right way.

Collectives™ on Stack Overflow

KMP String Matching Algorithm stuck in a loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related