KMP Pattern Matching Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of KMP prefix table computation

What is the output of the prefix table (lps array) after running the KMP preprocessing on the pattern "ABABCABAB"?

DSA Python

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 = "ABABCABAB"
lps = compute_lps(pattern)
print(lps)

A [0, 0, 1, 1, 0, 1, 2, 3, 4]

B [0, 1, 0, 1, 2, 3, 0, 1, 2]

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

D [0, 0, 1, 2, 0, 1, 2, 3, 4]

💡 Hint

Remember the prefix table stores the length of the longest prefix which is also suffix for each substring ending at index i.

The prefix table (lps array) for pattern "ABABCABAB" is computed by comparing characters and updating lengths of longest proper prefix which is also suffix. The correct lps array is [0, 0, 1, 2, 0, 1, 2, 3, 4].

❓ Predict Output

intermediate

KMP search output for pattern in text

What is the output of the following KMP search code when searching for pattern "ABAB" in text "ABABDABABABC"?

DSA Python

def kmp_search(text, 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
    
    i = 0
    j = 0
    result = []
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            result.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return result

text = "ABABDABABABC"
pattern = "ABAB"
print(kmp_search(text, pattern))

A [0, 5]

B [2, 5, 7]

C [0, 5, 7]

D [1, 3, 5]

💡 Hint

Check where the pattern fully matches in the text by comparing characters and using the prefix table.

The pattern "ABAB" appears starting at indices 0, 5, and 7 in the text "ABABDABABABC". The KMP algorithm finds these indices using the prefix table to skip unnecessary comparisons.

🧠 Conceptual

advanced

Understanding prefix table updates in KMP

During the computation of the prefix table (lps array) for the pattern "AAACAAAA", what is the value of the lps array at index 5?

A 2

B 3

C 1

D 0

💡 Hint

Remember lps[i] stores the length of the longest proper prefix which is also suffix for substring ending at i.

For pattern "AAACAAAA", the lps array is [0,1,2,0,1,2,3,4]. At index 5, the value is 3, indicating the longest prefix-suffix length for substring ending at index 5.

🔧 Debug

advanced

Identify the error in KMP prefix table code

What error will the following code produce when computing the prefix table for pattern "ABCDABD"?

DSA Python

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 = "ABCDABD"
print(compute_lps(pattern))

A IndexError

B SyntaxError

C TypeError

D [0, 0, 0, 0, 1, 2, 0]

💡 Hint

Check the line where length is updated inside the else block.

The code tries to access lps[length] without subtracting 1, which can cause an IndexError when length equals the length of the pattern prefix.

🚀 Application

expert

Number of pattern occurrences using KMP

Using KMP algorithm, how many times does the pattern "ABC" appear in the text "ABCABCABCABC"?

DSA Python

def kmp_search_count(text, 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
    
    i = 0
    j = 0
    count = 0
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            count += 1
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return count

text = "ABCABCABCABC"
pattern = "ABC"
print(kmp_search_count(text, pattern))

A 4

B 5

C 3

D 6

💡 Hint

Count how many times the pattern fully matches in the text.

The pattern "ABC" appears 4 times in the text "ABCABCABCABC" at indices 0, 3, 6, and 9.