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.

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) pattern matching algorithm?

easy

A. To calculate the factorial of a number recursively

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

D. To find occurrences of a pattern string within a text efficiently

Solution

1. Step 1: Understand the goal of KMP algorithm

   KMP is designed to search for a pattern inside a larger text efficiently without rechecking characters unnecessarily.

2. Step 2: Compare with other options

   Sorting, reversing strings, and factorial calculations are unrelated to pattern searching.

3. Final Answer:

   To find occurrences of a pattern string within a text efficiently -> Option D

4. Quick Check:

   KMP = Pattern search [OK]

Hint: KMP is about fast pattern search in text [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP calculates mathematical functions

2. Which of the following is the correct way to initialize the prefix table (lps array) in KMP algorithm in Python?

easy

A. lps = [0] * len(pattern)

B. lps = []

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

D. lps = None

Solution

1. Step 1: Understand the prefix table initialization

   The prefix table (lps array) stores lengths of longest proper prefix which is also suffix for each prefix of the pattern. It must be initialized with zeros for all positions.

2. Step 2: Check each option

   lps = [0] * len(pattern) correctly initializes lps with zeros for the entire pattern length. lps = [] is empty list, which is incomplete. lps = [1] * len(pattern) initializes with ones, which is incorrect. lps = None sets None, which is invalid.

3. Final Answer:

   lps = [0] * len(pattern) -> Option A

4. Quick Check:

   Prefix table starts with zeros [OK]

Hint: Prefix table starts with zeros for all pattern chars [OK]

Common Mistakes:

• Initializing lps with ones instead of zeros
• Leaving lps empty
• Assigning None to lps

3. What will be the output of the following Python code snippet using KMP algorithm?

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

pattern = "ABABC"
lps = compute_lps(pattern)
print(lps)

medium

A. [1, 0, 1, 0, 1]

B. [0, 0, 1, 2, 0]

C. [0, 1, 2, 3, 4]

D. [0, 0, 0, 0, 0]

Solution

1. Step 1: Compute lps array for pattern "ABABC"

   Index 0: lps[0] = 0 (always zero)
   Index 1: pattern[1] = 'B' != pattern[0] = 'A', lps[1] = 0
   Index 2: pattern[2] = 'A' == pattern[0] = 'A', lps[2] = 1
   Index 3: pattern[3] = 'B' == pattern[1] = 'B', lps[3] = 2
   Index 4: pattern[4] = 'C' != pattern[2] = 'A', lps[4] = 0

2. Step 2: Final lps array

   The computed lps array is [0, 0, 1, 2, 0].

3. Final Answer:

   [0, 0, 1, 2, 0] -> Option B

4. Quick Check:

   lps for "ABABC" = [0,0,1,2,0] [OK]

Hint: Match prefix and suffix lengths stepwise [OK]

Common Mistakes:

• Confusing lps values with pattern indices
• Assuming all zeros or all increasing values
• Mixing up characters when comparing

4. Identify the error in the following KMP prefix table computation code snippet:

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 0
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

medium

A. The loop should start with i = 1, not i = 0

B. The lps array should be initialized with ones

C. The length variable should start at 1

D. The function should return pattern instead of lps

Solution

1. Step 1: Analyze the loop initialization

   In KMP prefix table computation, the first character's lps is always zero and we start comparing from the second character, so i should start at 1.

2. Step 2: Check the given code

   The code starts with i = 0, which causes comparing pattern[0] with pattern[0] immediately, leading to incorrect lps values and infinite loop risk.

3. Final Answer:

   The loop should start with i = 1, not i = 0 -> Option A

4. Quick Check:

   Start i at 1 for prefix table [OK]

Hint: Start prefix loop from second character (i=1) [OK]

Common Mistakes:

• Starting loop at zero causing wrong comparisons
• Initializing lps with ones instead of zeros
• Returning wrong variable

5. Given the text "ABABDABACDABABCABAB" and pattern "ABABCABAB", how many times does the pattern appear in the text using KMP algorithm?

hard

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand the pattern and text

   The pattern "ABABCABAB" is searched inside the text "ABABDABACDABABCABAB" using KMP which efficiently finds all occurrences.

2. Step 2: Identify pattern occurrences

   By scanning the text:
   - Occurrence starts at index 10 (substring "ABABCABAB")
   So pattern appears 1 time.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Pattern appears once in text [OK]

Hint: Count all pattern matches including overlaps [OK]

Common Mistakes:

• Counting only first occurrence
• Ignoring overlapping matches
• Misreading pattern or text