advanced10 min read·Updated October 7, 2026

KMP Prefix Table (LPS) Explained: Tracing 'abab' and 'abacababab'

Master the KMP prefix table (LPS) with a complete walkthrough of 'abab' and 'abacababab'. Build the mental model, trace every shift, and avoid naive pitfalls.

By Learnisim AI·Published October 7, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • short strings
KMP Prefix Table (LPS) & Tracing 'abab' 1. The Redundancy Trap (Naive Search) Text: a b a b x a b Pattern: a b a c (Mismatch at 'c'!) Naive restarts from scratch on mismatch. Throws away matched prefix [a,b,a] & wastes O(N*M). 2. LPS Mental Model (Prefix == Suffix) Pattern: a b a b a Proper Prefixes: a, ab, aba, abab Proper Suffixes: a, ba, aba, baba Longest Proper Prefix == Suffix is 'aba' (len 3) Tells pointer exactly how far to slide forward! 3. Tracing LPS Construction & Table for Pattern 'a b a b' Index i = 0 Char: 'a' LPS[0] = 0 Index i = 1 Char: 'b' LPS[1] = 0 Index i = 2 Char: 'a' (Matches len 1) LPS[2] = 1 ('a' == 'a') Index i = 3 Char: 'b' (Matches len 2) LPS[3] = 2 ("ab" == "ab") 4. Practice: Predict Next State ('abacababab') On mismatch at 'c', use LPS table to jump len. Avoids re-scanning already validated prefixes. 5. Beyond Strings: Genomic Sequences DNA matching (A,C,T,G) & Substring Automata Accelerates pattern recognition in massive datasets.
KMP Prefix Table (LPS) Explained: Tracing 'abab' and 'abacababab' overview diagram
Why

Why Naive String Searching Wastes Work and How the LPS Table Fixes It

Phase 1: The Redundancy Trap in String Search

Imagine you need to search for the pattern inside a much larger text . A naive search algorithm compares character by character. When it hits a mismatch, it typically shifts the pattern by just one index and starts comparing all over again from the beginning of the pattern.
For instance, as we scan , we might match successfully against , but hit a mismatch at index 3 where has and has . A naive scan throws away all the intelligence it just gathered about the matching prefix and restarts the comparison right after the old starting point in .
In the worst case, this leads to an inefficient time complexity where every character in the text is repeatedly re-examined. We want an optimal way to skip redundant comparisons when a mismatch happens. The key to doing this without missing any potential matches is knowing how much of the current prefix overlaps with its own suffix.
This is where the Knuth-Morris-Pratt (KMP) algorithm's LPS array comes in. Before we search for in , or analyze another pattern like , we need to precompute a table that tells our search pointer exactly how far it can safely slide the pattern forward without losing any ground.
KMP Prefix Table (LPS) — Skipping Redundant WorkPhase 1: The Naive Trap vs. Smart Shift (Pattern: 'abababx')Text:abacabPattern:ababMismatch! (c vs b)Naive Shift: Shifts by +1 indexRe-checks 'ab' redundantly! O(n·m) worst case.KMP Shift: Uses LPS table to skip directly to index 2.Phase 2: Building the LPS (Longest Prefix which is also Suffix) Table for 'abababx'Pattern Index (i):0123456Pattern Char:abababxLPS Array [i]:0012340LPS[5] = 4 because prefix 'abab' == suffix 'abab'Phase 3: Tracing 'abacababab' LPS ComputationPattern:abacabababLPS Table:0010123456O(N) Time Complexity: Skips redundant comparisons cleanly!
Why Naive String Searching Wastes Work and How the LPS Table Fixes It diagram
Model

The LPS Mental Model: Longest Proper Prefix That Is Also Suffix

Phase 2:

Naive string search restarts from scratch every time a mismatch occurs. The KMP prefix table (LPS) solves this by pre-computing how much of the current match we can safely reuse. In our running example, consider the pattern . The LPS array (often called the table) has the exact same length as , where stores the length of the longest proper prefix of that is also a suffix of .
A proper prefix means a prefix that is strictly shorter than the substring itself (so for abab, the prefix cannot be abab itself). Let us evaluate this concept across our working example pattern and the alternative pattern . For index 0 in abab, the substring is a, which has no proper prefix matching its suffix, so . For index 1, the substring is ab, still 0. For index 2, the substring is aba, where the proper prefix a matches the suffix a, giving . For index 3, the substring is abab, where the proper prefix ab matches the suffix ab, giving .
When we switch to our second pattern, , the identical character streak forces the LPS values to increment steadily up to index 4: . That trailing c breaks the streak, dropping the value back down to 0. This table acts as a state machine. When a mismatch happens against the text , we do not shift our window by 1 and reset our text pointer; we consult the LPS value of the character just before the mismatch to instantly reposition our pattern pointer .
KMP Prefix Table (LPS) Mental Model & State Jump 1. Pattern p = "abab" (Proper Prefix = Suffix) a i=0, lps=0 b i=1, lps=0 a i=2, lps=1 b i=3, lps=2 prefix "ab" = suffix "ab" LPS Table for "abab" => [ 0, 0, 1, 2 ] 2. Pattern p = "aaaaac" (Streak & Break) a 0 a 1 a 2 a 3 a 4 c 0 LPS = [0, 1, 2, 3, 4, 0] Identical streak increments; trailing 'c' drops LPS to 0. 3. Search State Machine in Action: Searching "abab" in Text t = "abacababab" Text t: a b a c a b a b a b Pattern p: a b a b Mismatch! ('c' vs 'b') at j=3 Consult LPS Table before mismatch: • Character before mismatch: p[2] = 'a' (lps[2]=1) • Instead of resetting j=0 & shifting window by 1: • Instantly reposition pointer j = lps[2] = 1 Result: Safely reuses matched prefix "ab" instantly!
The LPS Mental Model: Longest Proper Prefix That Is Also Suffix diagram
Worked example

Tracing LPS Construction and String Matching for 'abab'

Phase 3: Worked Example

Now that we understand the proper prefix-suffix overlap, let's trace the construction of the KMP prefix table (LPS) for our running patterns, followed by searching p = "abab" inside t = "abacababab". Every step preserves known matches so we never back up in the text string t.

Given

- Pattern 1: p = "abab" ()
- Pattern 2: p = "aaaaac" ()
- Text: t = "abacababab" ()

Steps: Building LPS for "abab"

We maintain two pointers: len (length of the previous longest prefix suffix) and i (current character index starting at 1).
1. i = 0: lps[0] = 0. (Base case: a 1-character string has no proper prefix/suffix).
2. i = 1: p[1] ('b') != p[0] ('a'). Since len == 0, lps[1] = 0.
3. i = 2: p[2] ('a') == p[len] ('a'). len increments to 1. lps[2] = 1 ("a").
4. i = 3: p[3] ('b') == p[len] ('b'). len increments to 2. lps[3] = 2 ("ab").
Result for "abab": lps = [0, 0, 1, 2].

Steps: Building LPS for "aaaaac"

1. i = 0..4: Each character matches the running prefix, incrementing len sequentially up to 5.
- lps[0] = 0
- lps[1] = 1 ("a")
- lps[2] = 2 ("aa")
- lps[3] = 3 ("aaa")
- lps[4] = 4 ("aaaa")
2. i = 5: p[5] ('c') != p[len] ('a'). We fall back: len = lps[len-1] which is lps[3] = 3, then lps[2] = 2, and so on until mismatch or len == 0. Ultimately, lps[5] = 0 because no proper prefix matches the suffix ending in c.
Result for "aaaaac": lps = [0, 1, 2, 3, 4, 0].

Steps: Searching "abab" in "abacababab"

We align p against t using text pointer i_t = 0 and pattern pointer i_p = 0.
python
t = [a, b, a, c, a, b, a, b, a, b]
p = [a, b, a, b]
1. Indices 0 through 2: t[0..2] == p[0..2] ("aba"). i_p reaches 3.
2. Index 3: t[3] ('c') != p[3] ('b'). Mismatch! Instead of resetting i_t to 1, we consult lps[2] = 1. We set i_p = 1, keeping i_t = 3.
3. We resume matching at t[3] against p[1] ('b'), which fails (c != b), so i_p = lps[0] = 0 and i_t advances to 4.
4. Indices 4 through 7: t[4..7] matches p[0..3] ("abab") perfectly. i_p reaches 4, signaling a complete match.
Result: The first valid occurrence of "abab" in t is found at index 6 (the substring starting at t[6]).
python
def compute_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    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
Phase 3: Tracing LPS Construction & String Search for "abab" LPS Table Building: p = "abab" a i=0 b i=1 a i=2 b i=3 lps = [0, 0, 1, 2] i=2: matches p[0] (len=1) | i=3: matches p[1] (len=2) Resulting proper prefix-suffix lengths LPS Table Building: p = "aaaaac" Chars: a a a a a c lps: [0, 1, 2, 3, 4, 0] i=5 ('c'): len falls back via lps[3], lps[2]... No proper prefix matches suffix ending in 'c' => 0 Searching Pattern "abab" in Text "abacababab" t: a b a c a b a b a b 0 1 2 3 4 5 6 7 8 9 p: a b a b Key Takeaways from Search Trace • At t[3] ('c') != p[3] ('b'), mismatch occurs. • Consult lps[2] = 1; shift pattern without resetting i_t. • Perfect match found at t[4..7] -> index 6 start! Text pointer never backs up, guaranteeing O(n) time.
Tracing LPS Construction and String Matching for 'abab' diagram
Practice

Practice: Predict the Next State During KMP Matching

Phase 4: Practice

Let us put your understanding of the KMP prefix table (LPS) to the test using our ongoing working example. Recall that our pattern is p = "abab", which gave us the LPS array [0, 0, 1, 2], and our text is t = "abacababab". In the previous phase, we traced how p matched the prefix of t at indices 0..3 (abab), but encountered a mismatch at text index 2 (c vs b).
Now consider a later point in the search where the algorithm has successfully matched the prefix aba (indices 0..2 of p) against a segment of t, but the very next character in the text fails to match p[3]. Using your knowledge of how the LPS array dictates state jumps on mismatch, answer the challenge question below without fully re-running the entire naive scan.
python
# Pattern: p = "abab", LPS: [0, 0, 1, 2]
# Suppose our search pointer in p is currently at j = 3 (matching character 'b'),
# but the next character in text t mismatches p[3].
# What is the new value of j after consulting the LPS table?
Apply

Applying KMP Logic Beyond Strings: Genomic Sequences and Substring Automata

Phase 5: Transfer

Now that you have mastered building the LPS table for abab and aaaaac, and tracked how it skips redundant re-scans in abacababab, let us transfer this exact pattern-matching philosophy to a non-standard domain: genomic sequence analysis. Suppose you are scanning a massive DNA string t composed of nucleotides (A, C, G, T) for a specific regulatory motif pattern p = "ACAC". Just as with our text search, a naive sliding window would re-examine overlapping bases whenever a mismatch occurs at the fourth nucleotide. By constructing an LPS table for p = "ACAC" using the exact same prefix-suffix logic, you create a finite-state skip mechanism.
To see this in action, recall how our previous mismatch on abacababab allowed us to jump indices without resetting i to zero. In genomic streams, mutations or read errors demand high-throughput filtering where re-evaluating failed windows is computationally prohibitive. The KMP prefix table converts a linear search with backtracking into a linear-time streaming automaton. Whenever you encounter a motif search where patterns overlap with themselves, whether matching abab in text or ACAC in DNA, the LPS table guarantees you never step backward in the main data stream t.

Architectural Generalization

•Core Principle: Prefix tables store the history of internal pattern self-similarity so that mismatches do not destroy progress.

- Transfer Rule: Any domain featuring sequential window matching with potential overlaps can substitute a custom failure-function array derived identically to LPS.
- Complexity Bound: Preserves time complexity across alternative alphabets, provided the equality check for individual elements remains constant time.
python
def transfer_lps_concept():
    # Given a DNA motif pattern p = "ACAC"
    # Task: Write down its LPS array without running the full build loop.
    # Think about proper prefixes that are also suffixes for "ACAC".
    pass

FAQ

What is the LPS array for the pattern 'abab' in the KMP algorithm?
The LPS (Longest Proper Prefix which is also Suffix) array for 'abab' is [0, 0, 1, 2]. Index 0 has 0, index 1 ('ab') has 0, index 2 ('aba') has 1 ('a'), and index 3 ('abab') has 2 ('ab').
How does the KMP prefix table prevent re-scanning the text?
When a mismatch occurs, the LPS table tells us the exact length of the prefix that matches the suffix of the currently matched segment. Instead of resetting the text pointer, we simply shift the pattern pointer to the index specified by LPS[j-1].
What is the time complexity of building the LPS table and running KMP search?
Building the LPS table takes O(m) time, where m is the length of the pattern. The searching phase takes O(n) time, where n is the length of the text. Thus, the total time complexity is O(n + m).
What is the difference between a proper prefix and any prefix?
A proper prefix of a string is a prefix that is strictly shorter than the string itself. For example, the proper prefixes of 'aba' are '', 'a', and 'ab', excluding 'aba' itself.

Keep learning