KMP Pattern Matching Algorithm in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the prefix array with zeros.

DSA Python

lps = [[1]] * len(pattern)

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

A0

B1

C-1

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 1 or -1 instead of 0

Using None which causes errors

The prefix array (lps) should be initialized with zeros to store the longest prefix suffix lengths.

2fill in blank

medium

Complete the code to update the length of the previous longest prefix suffix.

DSA Python

if pattern[i] == pattern[length]:
    length += [1]

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

A-1

B1

C0

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Adding 0 or -1 which does not update length

Adding length itself causing wrong increments

When characters match, increase the length of the longest prefix suffix by 1.

3fill in blank

hard

Fix the error in the while loop condition to avoid infinite loops.

DSA Python

while i < len(text) and j < len(pattern):
    if text[i] == pattern[j]:
        i += 1
        j += 1
    else:
        if j != [1]:
            j = lps[j - 1]
        else:
            i += 1

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

A-1

B1

C0

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Checking j != 1 or j != -1 causing wrong behavior

Using length of pattern causing index errors

The check should be if j is not zero before updating j to avoid negative indexing.

4fill in blank

hard

Fill both blanks to correctly compute the prefix array (lps) for the pattern.

DSA Python

while i < len(pattern):
    if pattern[i] == pattern[[1]]:
        length += 1
        lps[i] = length
        i += 1
    else:
        if length != 0:
            length = lps[[2]]
        else:
            lps[i] = 0
            i += 1

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

Alength

Bi

Clength - 1

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i or i-1 instead of length or length-1

Mixing indices causing wrong prefix computation

Use 'length' to compare characters and 'length - 1' to update length when mismatch occurs.

5fill in blank

hard

Fill all three blanks to complete the KMP search function that returns all starting indices of pattern matches in text.

DSA Python

def kmp_search(text, pattern):
    lps = compute_lps(pattern)
    i = 0
    j = 0
    result = []
    while i < len(text):
        if text[i] == pattern[j]:
            i += [1]
            j += [2]
            if j == len(pattern):
                result.append(i - j)
                j = lps[[3]]
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return result

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

A1

Bj

Cj - 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing j by j or zero instead of 1

Resetting j incorrectly causing missed matches

Increment i and j by 1 when characters match. Reset j to lps[j-1] after a full match.