KMP Pattern Matching Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the length variable in the prefix function.

DSA C

int computeLPSArray(char* pat, int M, int* lps) {
    int len = [1];
    int i = 1;
    lps[0] = 0;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return 0;
}

Drag options to blanks, or click blank then click option'

A1

B0

CM

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing len to 1 causes incorrect prefix length calculation.

Using -1 or M leads to out-of-bound errors.

The length variable 'len' should start at 0 because initially there is no proper prefix which is also suffix.

2fill in blank

medium

Complete the code to reset the index i in the KMP search function after a mismatch.

DSA C

void KMPSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    int lps[M];
    computeLPSArray(pat, M, lps);
    int i = 0; // index for txt[]
    int j = 0; // index for pat[]
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            printf("Found pattern at index %d\n", i - j);
            j = lps[[1]];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
}

Drag options to blanks, or click blank then click option'

AM - 1

Bi

Cj - 1

Dlps[j - 1]

Attempts:

3 left

💡 Hint

Common Mistakes

Resetting j to i or M-1 causes incorrect search continuation.

Using lps[j] instead of lps[j-1] leads to wrong index.

After finding a pattern, j is reset to lps[j-1] to continue searching for next matches.

3fill in blank

hard

Fix the error in the prefix function loop condition to avoid infinite loop.

DSA C

int computeLPSArray(char* pat, int M, int* lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;
    while ([1]) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return 0;
}

Drag options to blanks, or click blank then click option'

Ai < M

Blen < M

Ci <= M

Dlen <= M

Attempts:

3 left

💡 Hint

Common Mistakes

Using i <= M causes out-of-bound access.

Using len < M is incorrect because len is prefix length, not index.

The loop should run while i is less than M to avoid accessing out of bounds and infinite loops.

4fill in blank

hard

Fill both blanks to correctly update indices after mismatch in KMPSearch.

DSA C

void KMPSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    int lps[M];
    computeLPSArray(pat, M, lps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        } else {
            if (j != 0) {
                j = [1];
            } else {
                i = [2];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Alps[j - 1]

Bi + 1

Cj - 1

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting j to j-1 causes wrong prefix reuse.

Incrementing i incorrectly leads to skipping characters.

On mismatch, j is reset to lps[j-1] to reuse prefix info; if j is zero, i moves forward by one.

5fill in blank

hard

Fill all three blanks to complete the prefix function initialization and loop.

DSA C

int computeLPSArray(char* pat, int M, int* lps) {
    int len = [1];
    int i = [2];
    lps[0] = 0;
    while (i [3] M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return 0;
}

Drag options to blanks, or click blank then click option'

A0

B1

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Starting i at 0 causes infinite loop.

Using '<=' in loop condition causes out-of-bound errors.

len starts at 0, i starts at 1, and loop runs while i < M to process all pattern characters.