1
$\begingroup$

When building the partial match table for KMP:

void buildBackTable() { 
    int i = 0, j = -1; b[0] = -1; 
    while (i < m) { 
        while (j >= 0 && P[i] != P[j]) j = b[j]; //Why is this a while loop!?
        i++; j++;
        b[i] = j;
    }
}   

How come that second while loop is not a conditional instead? Such as:

void buildBackTable() { 
    int i = 0, j = -1; b[0] = -1; 
    while (i < m) { 
        if (j >= 0 && P[i] != P[j]) j = b[j]; //Why not?
        i++; j++;
        b[i] = j;
    }
}   

In most of the examples I've tried, this statement is used to reset j to -1 when there is no match, so when the next iteration comes, we compare the first character of the string (P[j]) with the character at position i (P[i]). Is there an example where the while loop would be needed? I would love to see one. I've tried several samples of my own and changing the statement to a conditional would not make a difference (hence my question).

$\endgroup$
1
  • 1
    $\begingroup$ Have you tried random testing to search for an example where it makes a difference? e.g., instrument your code to see if the while loop ever executes more than one iteration; generate one million random test cases on short strings; and run your code on all of those test cases to see if it ever trips the instrumentation. That might help you form a conjecture. (If you want to get sophisticated, if none of the test cases finds an example where it makes a difference, you could even try using Klee to search more systematically for examples.) $\endgroup$ – D.W. Aug 5 '16 at 0:46

Your Answer

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

Browse other questions tagged or ask your own question.