🔎 String Matching

Knuth–Morris–Pratt (KMP) — Interactive Visualizer

Learn LPS / π array, practice it yourself, and then watch how KMP uses that information to search efficiently in O(n + m).

Topic: KMP

Why KMP? — clean intuition first

The whole motivation of KMP can be taught with one sentence: do not re-check what you already know. This tab shows that idea in four simple stages.

Current stage

1 / 4

Main takeaway

Naive restarts and repeats work

Step 1 — Naive mismatch

We matched several characters and then hit a mismatch.

Text

Pattern

Next comparison will be shown here.

Student thinking checkpoint

Press Next to begin the guided story.

💡 Bridge to LPS

KMP comes from a simple question: Can some part of the matched pattern still be useful after mismatch?

Naive thinking

“We got a mismatch. Let us restart from the next text position.”

KMP thinking

“We already matched many characters. Maybe some suffix of that match is also a prefix of the pattern.”

LPS / π Builder

Step through pattern preprocessing and watch the fallback logic carefully.

Pattern

Current Match Mismatch / fallback

Pointer i

Current len

Press Build Full LPS or step through it.

Pseudocode Trace — Build LPS

lps[0] = 0 len = 0 i = 1 while i < m: if pattern[i] == pattern[len]: len++ lps[i] = len i++ else: if len != 0: len = lps[len - 1] else: lps[i] = 0 i++

Read the highlighted line with the current values of i and len. This makes the fallback logic much easier to follow.

Try Your Own π / LPS Array

Enter the π values yourself and check each index.

Pattern

Generate the pattern boxes, enter values, then check.

Reminder

For each index i, inspect pattern[0..i]. Ask: What is the longest proper prefix that is also a suffix?

It must be both a prefix and a suffix.
The whole string is not allowed because the prefix must be proper.
When mismatch happens, think fallback — not restart.

KMP Matching Visualizer

Use the LPS array during search and watch how pointers move.

Text

Pattern

Text pointer i

Pattern pointer j

Current pattern LPS

Run or step through KMP matching.

Pseudocode Trace — KMP Matching

buildLPS(pattern) i = 0, j = 0 while i < n: if text[i] == pattern[j]: i++ j++ if j == m: report match at i - j j = lps[j - 1] else if i < n and text[i] != pattern[j]: if j != 0: j = lps[j - 1] else: i++

Watch how the highlighted line changes when KMP finds a match, hits a mismatch with j ≠ 0, or must advance i.

Naive vs KMP Comparison

Compare the number of character comparisons on the same input.

Text

Pattern

Naive comparisons

KMP comparisons

Run the comparison to see the difference.

Interpretation

Naive rechecks. KMP reuses. That is the heart of O(n + m).

Build LPS

buildLPS(pattern):
    lps[0] = 0
    len = 0
    i = 1

    while i < m:
        if pattern[i] == pattern[len]:
            len++
            lps[i] = len
            i++
        else:
            if len != 0:
                len = lps[len - 1]
            else:
                lps[i] = 0
                i++

KMP Search

KMP(text, pattern):
    buildLPS(pattern)
    i = 0, j = 0

    while i < n:
        if text[i] == pattern[j]:
            i++, j++

        if j == m:
            report match at i - j
            j = lps[j - 1]
        else if i < n and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i++

Quick revision

LPS / π stores useful prefix information.
KMP never moves the text pointer backward.
Pattern pointer jumps using LPS on mismatch.
Total time complexity = O(n + m).

One-line memory trick

KMP does not start over blindly. It remembers how much of the pattern is still useful.