Knuth-Morris-Pratt Algorithm in Swift

This algorithm is useful for finding matching patterns in a string.
The concept is very clever, but I found it difficult to understand at first. So, I decided to visualize it

First, Let’s learn what LPS is

LPS is the length of the longest prefix that is also a suffix,
excluding the entire string itself.

In the Wikipedia about the KMP algorithm this concept is described as a KMP table.

For this article, I will call it the LPS array, because this is the term commonly used in many LeetCode explanations.

Pattern is A B A B C A B A B

LPS is 0 0 1 2 0 1 2 3 4

Huh? Let’s focus on how to implement the LPS function first. Then, I’ll explain why LPS is important in the KMP algorithm.

The LPS value at each position represents the length of the longest proper prefix that is also a suffix.

func lps(pattern: String) -> [Int] {
    let pattern = Array(pattern)
    let count = pattern.count
    
    var lps = Array(repeating: 0, count: count)
    var i = 0
    var j = 1
    
    while j < count {
        if pattern[i] == pattern[j] {
            i += 1
            lps[j] = i
            j += 1
        } else {
            if i != 0 {
                i = lps[i - 1]
            } else {
                lps[j] = 0
                j += 1
            }
        }
    }
    return lps
}

First, we create an LPS array filled with zeros. We start comparing from index 1 because the LPS value at index 0 is always zero.

At index 2, pattern[i] and pattern[j] are both A. Since they match, we increase i and store 1 in lps[2]

At index 3, B matches B again. The matching prefix now has length 2, so lps[3] becomes 2.

At index 4, A and C do not match. Because i is not zero, we use the previously calculated LPS value to try a shorter prefix.

After falling back, i becomes zero, but C still does not match A. Therefore, lps[4] remains 0, and we move to the next index.

At index 5, A matches the prefix character A. We store 1 in lps[5] and move both pointers forward.

At index 6, B matches B. The matching prefix has length 2, so lps[6] becomes 2.

At index 7, A matches A once more. The matching prefix is now ABA, so lps[7] becomes 3.

At index 8, B matches B. The longest matching prefix and suffix are both ABAB, so lps[8] becomes 4.

All characters have been processed. The completed LPS array is [0, 0, 1, 2, 0, 1, 2, 3, 4]

How KMP Algorithm work?

We know what LPS is. Let’s use it in KMP algorithm.

Text. : ABABDABABCABAB

Pattern: ABABCABAB

Output: True

func isMatching(text: String, pattern: String) -> Bool {
    let textCharacters = Array(text)
    let patternCharacters = Array(pattern)
    guard !patternCharacters.isEmpty else {
        return true
    }
    let lpsTable = lps(pattern: pattern)
    var textIndex = 0
    var patternIndex = 0
    while textIndex < textCharacters.count {
        if textCharacters[textIndex] == patternCharacters[patternIndex] {
            textIndex += 1
            patternIndex += 1
            if patternIndex == patternCharacters.count {
                let startIndex = textIndex - patternIndex
                print("Pattern found at index \(startIndex)")
                return true
            }
        } else if patternIndex != 0 {
            patternIndex = lpsTable[patternIndex - 1]
        } else {
            textIndex += 1
        }
    }
    return false
}
isMatching(text: "ABABDABABCABAB", pattern: "ABABCABAB")

We start with both indexes at 0. The first character, A, matches, so both indexes move forward

B matches B, so we continue comparing the next characters in the text and the pattern.

A matches A again. Three characters have now matched successfully

B also matches B, so the matched part is now ABAB

The next characters do not match: the text has D, but the pattern expects C. Because some characters (ABAB) already matched, we use the LPS table.

The LPS value tells us to move the pattern index back from 4 to 2. The text index stays at 4, so we do not recheck the text.

The comparison still fails with D and A. Since the pattern index is now 0, there is no shorter prefix to reuse.

We move the text index forward to 5. The text character A now matches the first character of the pattern.

B matches B, so both indexes move forward again.

A matches A. The matching section is growing from the new starting position.

B matches B, so four characters have matched from text index 5

C matches C. The pattern continues to match without restarting.

A matches A, and the matched part is now ABABCA

B matches B. The pattern index moves to 6

A matches A again. Only the final character remains.

The final B matches B. The entire pattern has now been matched.

The pattern was found at index 5. We calculated the starting index using textIndex – patternIndex, which is 14 – 9 = 5

Full Source Code

import Foundation
func lps(pattern: String) -> [Int] {
    let pattern = Array(pattern)
    let count = pattern.count
    
    var lps = Array(repeating: 0, count: count)
    var i = 0
    var j = 1
    
    while j < count {
        if pattern[i] == pattern[j] {
            i += 1
            lps[j] = i
            j += 1
        } else {
            if i != 0 {
                i = lps[i - 1]
            } else {
                lps[j] = 0
                j += 1
            }
        }
    }
//    print("""
//        Input : \(pattern)
//        Result: \(lps.compactMap { String($0) })
//        """
//    )
    return lps
}
func isMatching(text: String, pattern: String) -> Bool {
    let textCharacters = Array(text)
    let patternCharacters = Array(pattern)
    guard !patternCharacters.isEmpty else {
        return true
    }
    let lpsTable = lps(pattern: pattern)
    var textIndex = 0
    var patternIndex = 0
    while textIndex < textCharacters.count {
        if textCharacters[textIndex] == patternCharacters[patternIndex] {
            textIndex += 1
            patternIndex += 1
            if patternIndex == patternCharacters.count {
                let startIndex = textIndex - patternIndex
                print("Pattern found at index \(startIndex)")
                return true
            }
        } else if patternIndex != 0 {
            patternIndex = lpsTable[patternIndex - 1]
        } else {
            textIndex += 1
        }
    }
    return false
}
isMatching(text: "ABABDABABCABAB", pattern: "ABABCABAB")

Time Complexity and Space Complexity

Let n be the length of the text and m be the length of the pattern.

Time Complexity

According to Wikipedia, KMP has two main phases:

• Preprocessing the pattern – LPS Table: O(m)
• Searching the text: O(n)

Building the LPS table takes O(m) time because we process each character in the pattern.

Searching for the pattern takes O(n) time. The text index never moves backward, and the pattern index uses the LPS Table when a mismatch occurs.

Therefore, the total time complexity is:

O(n+m)

Space Complexity

//Space: O(n)
let textCharacters = Array(text)
//Space: O(m)
let patternCharacters = Array(pattern)
//Space: O(m)
let lpsTable = lps(pattern: pattern)

The textCharacters uses O(n) space, and the pattern and LPS table use O(m) space.

Therefore, this Swift implementation uses O(n+m) space in total

Conclusion

KMP looked difficult to me at first, especially the LPS table. After visualizing each step, I could understand how KMP reuses previously matched characters instead of starting over.

There are simpler approaches, such as brute force, built-in search, and Rabin-Karp.

Next time, I’ll introduce the Rabin-Karp algorithm.