Understanding Algorithms (Strings And Pattern Matching), Part 29: Knuth–Morris–Pratt Algorithm (KMP Algorithm).

Knuth–Morris–Pratt Algorithm (KMP Algorithm) improves string matching by avoiding repeated comparisons using a prefix (LPS) table. Instead of restarting from scratch after a mismatch, it reuses previous matches, giving an efficient time complexity of O(n + m).

The KMP Algorithm solves the same problem as naive string matching: finding all occurrences of a pattern inside a larger text. The difference is how it handles mismatches. Instead of restarting comparisons from scratch, KMP reuses information from previous matches. This single idea removes massive redundancy.

Given a text T of length n and a pattern P of length m, naive matching compares characters repeatedly and may take O(n × m) time. KMP guarantees O(n + m) time by ensuring that each character in the text is examined at most once.

The core insight behind KMP is simple but powerful. When a mismatch occurs, some of the characters you already matched do not need to be rechecked.

To make this work, KMP preprocesses the pattern and builds an auxiliary array called the LPS array (Longest Proper Prefix which is also Suffix).

The LPS array captures internal structure of the pattern.

For every index i in the pattern, LPS[i] = length of the longest proper prefix of P[0…i] that is also a suffix of P[0…i].

“Proper prefix” means the whole string is excluded. Only shorter prefixes are considered. Lets take the pattern to be ABABCABAB. Hence, the LPS array becomes [0, 0, 1, 2, 0, 1, 2, 3, 4].

Each value tells you how much of the pattern can be reused after a mismatch. This preprocessing step takes O(m) time.

Once LPS is built, the actual matching begins.

Two pointers are used, i for the text and j for the pattern. Characters T[i] and P[j] are compared. If they match, both pointers move forward.

If they mismatch, and if j ≠ 0, set j = LPS[j−1]. If j = 0, move i forward.

Notice what happens here. The text pointer i never moves backward. Only the pattern pointer jumps using LPS. This is the key to linear performance.

Instead of shifting the pattern by one position like naive search, KMP jumps directly to the next valid alignment based on prefix–suffix information. Previously matched characters are reused logically, without re-comparing them.

This mechanism ensures that each character of the text is processed once. Each character of the pattern is processed once.

Hence the time complexiity turns out to be O(n + m), and space complexity turns out to be O(m).

The LPS array is what transforms brute-force searching into structured searching. Conceptually, KMP treats the pattern as a small automaton. Every mismatch transitions the algorithm into a new state determined by LPS. The pattern effectively “remembers” its own structure.

This is fundamentally different from naive matching, which forgets everything after a mismatch.

KMP performs especially well on patterns with repeated prefixes, such as AAAA, ABABAB, ABCABC. These patterns cause naive algorithms to repeatedly compare the same characters. KMP avoids that completely.

Another important property is that KMP never backs up in the text. This makes it suitable for streaming data, where characters arrive sequentially and cannot be revisited. Log scanning, packet inspection, and DNA sequence processing often rely on this behavior.

From an implementation perspective, most of the difficulty lies in building the LPS array correctly. Once LPS is understood, the matching phase becomes mechanical.

Algorithmically, KMP introduces several major ideas like pattern preprocessing, state reuse after mismatch, linear-time string matching, and prefix–suffix relationships

It is often the first algorithm where students encounter the idea that work done earlier can guide future decisions, instead of being discarded. KMP also changes how string problems are approached. Instead of treating patterns as passive input, KMP treats the pattern as an active structure that controls search behavior.

More advanced string algorithms, such as Z-algorithm and suffix-based methods, build on the same principle: extract internal structure first, then match efficiently.

KMP demonstrates that optimization does not always come from faster hardware or clever tricks. Sometimes it comes from understanding the problem deeply enough to stop repeating yourself. By encoding what the pattern already knows about itself, KMP turns repeated failures into forward progress, converting quadratic behavior into predictable linear performance.

class KMPStringMatching:
    def __init__(self):
        """
        Initializes KMP String Matching.

        What KMP fixes:
        - Naive matching rechecks characters unnecessarily.
        - KMP remembers previous matches.

        Core idea:
        - Preprocess the pattern.
        - Build LPS (Longest Prefix Suffix) array.
        - Use it to skip comparisons safely.
        """

        pass

    # --------------------------------------------------
    # BUILD LPS ARRAY
    # --------------------------------------------------
    def build_lps(self, pattern):
        """
        Builds Longest Prefix Suffix (LPS) array.

        Meaning of LPS[i]:
        - Length of longest proper prefix of pattern[0..i]
          which is also a suffix.

        Why this matters:
        - Tells how much we can shift pattern on mismatch.
        - Prevents rechecking matched characters.
        """

        m = len(pattern)
        lps = [0] * m

        length = 0   # length of previous longest prefix
        i = 1

        while i < m:

            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

    # --------------------------------------------------
    # KMP SEARCH
    # --------------------------------------------------
    def kmp_search(self, text, pattern):
        """
        Performs KMP string matching.

        Strategy:
        - Use LPS to avoid restarting comparisons.
        - Never move text pointer backward.

        Time Complexity:
        - O(n + m)
        """

        n = len(text)
        m = len(pattern)

        lps = self.build_lps(pattern)

        i = 0   # index for text
        j = 0   # index for pattern

        matches = []

        while i < n:

            # Characters match → move both pointers
            if text[i] == pattern[j]:
                i += 1
                j += 1

            # Full pattern matched
            if j == m:
                matches.append(i - j)
                j = lps[j - 1]

            # Mismatch after some matches
            elif i < n and text[i] != pattern[j]:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1

        return matches

# --------------------------------------------------
# EXAMPLE USAGE
# --------------------------------------------------

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

kmp = KMPStringMatching()

positions = kmp.kmp_search(text, pattern)

print("Pattern found at indices:", positions)