Day 56: String Algorithms - Knuth-Morris-Pratt (KMP)#

Welcome to Day 56 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Knuth-Morris-Pratt (KMP) algorithm, an efficient string matching algorithm that improves upon the naive approach for finding a pattern within a text.

What is the KMP Algorithm?#

The Knuth-Morris-Pratt (KMP) algorithm is a string matching algorithm that searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

How KMP Works#

The key idea behind KMP is to utilize the information gained by previous match attempts to skip redundant comparisons. It does this by pre-processing the pattern to create a “failure function” or “partial match table” that is used to skip characters in the input string.

The algorithm consists of two main steps:

1. Preprocessing: Create the failure function for the pattern.
2. Searching: Use the failure function to perform the actual search.

Implementation#

Here’s a Python implementation of the KMP algorithm:

 1def compute_lps(pattern):
 2    lps = [0] * len(pattern)
 3    length = 0
 4    i = 1
 5
 6    while i < len(pattern):
 7        if pattern[i] == pattern[length]:
 8            length += 1
 9            lps[i] = length
10            i += 1
11        else:
12            if length != 0:
13                length = lps[length - 1]
14            else:
15                lps[i] = 0
16                i += 1
17
18    return lps
19
20def kmp_search(text, pattern):
21    M = len(pattern)
22    N = len(text)
23
24    lps = compute_lps(pattern)
25
26    i = j = 0
27    results = []
28
29    while i < N:
30        if pattern[j] == text[i]:
31            i += 1
32            j += 1
33        
34        if j == M:
35            results.append(i - j)
36            j = lps[j - 1]
37        elif i < N and pattern[j] != text[i]:
38            if j != 0:
39                j = lps[j - 1]
40            else:
41                i += 1
42
43    return results
44
45# Example usage
46text = "ABABDABACDABABCABAB"
47pattern = "ABABCABAB"
48matches = kmp_search(text, pattern)
49print(f"Pattern found at indices: {matches}")

Time Complexity#

• Preprocessing: O(m), where m is the length of the pattern
• Searching: O(n), where n is the length of the text

The total time complexity is O(m + n), which is a significant improvement over the naive approach’s O(mn) complexity.

Space Complexity#

The space complexity is O(m) for storing the failure function.

Advantages of KMP#

1. Efficient for long patterns and texts
2. No backtracking in the main text
3. Performs well when the pattern has many repeating subpatterns

Disadvantages of KMP#

1. Requires preprocessing of the pattern
2. More complex to implement compared to naive approach
3. Not as efficient for short patterns or texts

Applications of KMP#

1. Text editors for finding and replacing patterns
2. Intrusion detection in computer networks
3. Computational biology for finding DNA sequences
4. Spam filtering in email systems

Variations and Related Algorithms#

1. Boyer-Moore algorithm: Another efficient string matching algorithm
2. Rabin-Karp algorithm: Uses hashing to find patterns
3. Aho-Corasick algorithm: Finds multiple patterns simultaneously

Exercise#

1. Modify the KMP algorithm to find all non-overlapping occurrences of the pattern in the text.
2. Implement a function that uses KMP to determine if a string is a rotation of another string.
3. Use KMP to solve the problem of finding the longest prefix which is also a suffix in a given string.

Summary#

Today, we explored the Knuth-Morris-Pratt (KMP) algorithm, an efficient string matching algorithm that improves upon the naive approach. We implemented the algorithm, discussed its time and space complexity, and looked at its advantages, disadvantages, and applications.

Understanding string matching algorithms like KMP is crucial for many text processing tasks and forms the basis for more advanced string algorithms. As we progress through this challenge, you’ll see how these concepts can be applied to solve various string-related problems efficiently.

Tomorrow, we’ll dive into another important string matching algorithm: the Rabin-Karp Algorithm. Stay tuned!

Solution#

 1# Exercise 2: Use KMP to check whether s2 is a rotation of s1.
 2# A rotation of s1 is always a substring of s1 + s1, so we KMP-search there.
 3def compute_lps(pattern):
 4    lps = [0] * len(pattern)
 5    length = 0
 6    i = 1
 7    while i < len(pattern):
 8        if pattern[i] == pattern[length]:
 9            length += 1
10            lps[i] = length
11            i += 1
12        elif length != 0:
13            length = lps[length - 1]  # Fall back in the pattern.
14        else:
15            lps[i] = 0
16            i += 1
17    return lps
18
19def kmp_contains(text, pattern):
20    if not pattern:
21        return True
22    lps = compute_lps(pattern)
23    i = j = 0
24    while i < len(text):
25        if text[i] == pattern[j]:
26            i += 1
27            j += 1
28            if j == len(pattern):
29                return True
30        elif j != 0:
31            j = lps[j - 1]
32        else:
33            i += 1
34    return False
35
36def is_rotation(s1, s2):
37    return len(s1) == len(s2) and kmp_contains(s1 + s1, s2)
38
39print(is_rotation("waterbottle", "erbottlewat"))  # True
40print(is_rotation("hello", "lloeh"))              # False