Loading…

mediumStringsFrequently asked

Pattern Search — KMP (Knuth–Morris–Pratt)

Q: How do you solve Pattern Search — KMP (Knuth–Morris–Pratt) using the Naive — Slide and Re-Compare approach?

When to use it: Open with this to anchor the complexity discussion — it makes the O(n + m) of KMP feel earned. Place the pattern at the first position of the text and compare character by character. The moment a character disagrees, shift the pattern one step to the right and start the comparison over from the pattern's first character. **Why it's the obvious first attempt.** The definition of 'p occurs at index s' is literally 't[s..s+m-1] == p'. Checking that definition directly — one alignment at a time, one character at a time — needs no insight at all. It's the brute-force translation of the problem statement. **Where the waste lives.** Suppose you've matched `j` characters of the pattern and then hit a mismatch. Naive matching discards all `j` of those confirmed matches: it bumps the start position by one and resets the pattern index to `0`, re-reading text characters it already looked at. Those re-reads are the redundant work KMP eliminates. **The worst case that exposes it.** Take `t = "aaaaaaaaab"` and `p = "aaab"`. At nearly every alignment you match `aaa` (three characters) before the final `b` fails, then slide by one and repeat. That's about `n` alignments each doing `m` comparisons — quadratic. For `n = m = 10⁶` that's 10¹² operations, far past what runs in time. Time complexity: O(n·m). Space complexity: O(1).

Arrays & Hashing · 39 of 83 · 12 min

Given a text string t of length n and a pattern string p of length m, return all starting indices i (0-based) such that t[i..i+m-1] == p.

Occurrences may overlap (e.g. pattern aa in text aaaa occurs at indices 0, 1, 2). If the pattern never appears, return an empty list.

In plain English

You're locating a needle inside a haystack and reporting every position. The naive method re-checks characters it already compared after each mismatch; KMP's job is to never re-examine a text character, by remembering how much of the pattern's own prefix is reusable when a mismatch happens.

Examples

Example 1

Input: t = "abxabcabcaby", p = "abcaby"
Output: [6]
Note: The pattern matches t[6..11] = "abcaby". The earlier "abc" runs are partial matches that KMP recovers from without rescanning the text.

Example 2

Input: t = "aaaa", p = "aa"
Output: [0, 1, 2]
Note: Overlapping matches. After a hit, j = lps[j-1] = 1 keeps one character of overlap instead of restarting.

Example 3

Input: t = "abcde", p = "fg"
Output: []
Note: No occurrence — the result is empty, not an error.

Constraints

1 ≤ m ≤ n ≤ 10⁶
Strings consist of printable ASCII characters
Overlapping occurrences must all be reported
An empty pattern is out of scope — assume m ≥ 1

Clarifying questions4First question: Do overlapping matches count as separate occurrences?Explore questions

Q1.Do overlapping matches count as separate occurrences?
Yes by default — `aa` in `aaaa` is three matches. Confirm this, because it changes whether you reset `j` to 0 or to `lps[j-1]` after a hit.
Q2.Are we matching a single pattern or many?
Single. If many patterns share one text, Aho–Corasick (a multi-pattern generalization of KMP) is the right tool.
Q3.Case-sensitive and full character set?
Assume case-sensitive ASCII unless told otherwise. KMP doesn't care about alphabet size — it compares characters directly.
Q4.Return indices or just a count / boolean?
Indices here. The algorithm is identical; you just collect instead of returning early.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find every starting index where pattern `p` occurs in text `t`. Naive sliding comparison is O(n·m) because a mismatch throws away everything you learned. KMP precomputes an LPS (longest proper prefix that is also a suffix) array for the pattern in O(m), then scans the text once in O(n) — never moving the text pointer backward. Total O(n + m).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand why naive matching is quadratic and can articulate the failure-function insight — that a partial match already encodes how much of the pattern is reusable.

Where candidates slip

Building the LPS array wrong: advancing the index on the fall-back branch, or confusing 'prefix that is also a suffix' with simple character repetition.

How to stand out

State the text-pointer-never-moves-back invariant explicitly, derive the LPS recurrence out loud, and mention that lps[m-1] reveals the pattern's smallest period.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive — Slide and Re-Compare	`O(n·m)`	`O(1)`	Open with this to anchor the complexity discussion — it makes the O(n + m) of KMP feel earned.	Read
2	KMP — LPS Failure Function (Optimal)Optimal	`O(n + m)`	`O(m)`	The answer they want. Lead with the invariant 'the text pointer never moves backward', then explain the LPS table that makes it possible.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMismatch at text i, pattern jApproach?NaiveKMPExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive — Slide and Re-Compare

TimeO(n·m)SpaceO(1)

Open with this to anchor the complexity discussion — it makes the O(n + m) of KMP feel earned.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Try aligning the pattern at every possible start position s from 0 to n−m. For each start, compare characters until a mismatch or a full match.

2Hint 2Explore hint

What do you throw away when a mismatch happens at offset j? All j characters you just confirmed matched — you reset to start s+1 and begin again at j=0.

3Hint 3Explore hint

Count the worst case: text 'aaaa...a' with pattern 'aaa...ab'. Almost every alignment matches m−1 characters before failing on the last.

A · Core idea

Place the pattern at the first position of the text and compare character by character. The moment a character disagrees, shift the pattern one step to the right and start the comparison over from the pattern's first character.

Why it's the obvious first attempt. The definition of 'p occurs at index s' is literally 't[s..s+m-1] == p'. Checking that definition directly — one alignment at a time, one character at a time — needs no insight at all. It's the brute-force translation of the problem statement.

Where the waste lives. Suppose you've matched j characters of the pattern and then hit a mismatch. Naive matching discards all j of those confirmed matches: it bumps the start position by one and resets the pattern index to 0, re-reading text characters it already looked at. Those re-reads are the redundant work KMP eliminates.

The worst case that exposes it. Take t = "aaaaaaaaab" and p = "aaab". At nearly every alignment you match aaa (three characters) before the final b fails, then slide by one and repeat. That's about n alignments each doing m comparisons — quadratic. For n = m = 10⁶ that's 10¹² operations, far past what runs in time.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "abxabc", p = "abc"

Array state

s=0

matches ab, fails on x≠c

s ↓

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result[3]

C · Code with teaching comments

Reference implementation previewimport java.util.ArrayList; import java.util.List; public class NaiveSearch { public List<Integer> search(String t, String p) {Explore the full code

solution.javaJava

Naive — Slide and Re-Compare — reference

3 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class NaiveSearch {
5
    public List<Integer> search(String t, String p) {
6
        List<Integer> result = new ArrayList<>();
7
        int n = t.length(), m = p.length();
8
        // Try every alignment whose end stays inside the text — s ranges over n−m+1
9
        // positions.
10
        for (int s = 0; s + m <= n; s++) {
11
            int j = 0;
12
            // Compare from the pattern's start each time — this restart is the source
13
            // of the quadratic cost.
14
            while (j < m && t.charAt(s + j) == p.charAt(j)) {
15
                j++;
16
            }
17
            if (j == m) {
18
                result.add(s);
19
            }
20
        }
21
        return result;
22
    }
23
 
24
    public static void main(String[] args) {
25
        System.out.println(new NaiveSearch().search("abxabc", "abc"));
26
    }
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proof

Every mismatch in the naive method throws away a confirmed partial match. That discarded prefix is not garbage — it's information about the pattern's own structure. KMP's entire contribution is refusing to throw it away.

ComplexityO(n·m) time, O(1) space — There are up to n−m+1 alignments, and each can compare up to m characters before failing → (n−m+1)·m ≈ n·m in the worst case. No extra memory beyond a couple of indices.

E · Edge cases and pitfalls3Looping s up to n instead of n−m → out-of-bounds reads near the end.Explore edge cases

Pitfalls

Looping s up to n instead of n−m → out-of-bounds reads near the end.
Claiming this is 'usually fine' — on adversarial inputs it is genuinely O(n·m).
Forgetting overlapping matches still work here only because you slide by exactly one.

03.2

Approach 2 of 2 · Optimal

KMP — LPS Failure Function (Optimal)

TimeO(n + m)SpaceO(m)

The answer they want. Lead with the invariant 'the text pointer never moves backward', then explain the LPS table that makes it possible.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When a mismatch happens after matching j characters, those j matched characters equal p[0..j-1]. Is there a proper prefix of that matched chunk that is also a suffix of it? If so, that prefix is already aligned with the text — you can resume from there without moving the text pointer.

2Hint 2Explore hint

Define lps[k] = length of the longest proper prefix of p[0..k] that is also a suffix. Precompute it for the whole pattern in O(m).

3Hint 3Explore hint

During the scan, on a mismatch set j = lps[j-1] (fall back within the pattern) and keep the text index i where it is. On a match advance both; on a full match record i−m and set j = lps[j-1].

A · Core idea

KMP runs in two phases: preprocess the pattern into an LPS array, then scan the text once.

What LPS actually stores. lps[k] is the length of the longest proper prefix of p[0..k] that is simultaneously a suffix of p[0..k]. 'Proper' means it isn't the whole substring. For p = "abcaby", lps = [0,0,0,1,2,0]: at index 4 ("abcab") the prefix "ab" is also the suffix "ab", so lps[4] = 2.

Why that array is exactly what a mismatch needs. Imagine you've matched the first j characters of the pattern against the text and then character p[j] disagrees with the text. The j matched characters are precisely p[0..j-1]. You'd like to slide the pattern forward as far as possible while keeping a valid partial match. The longest run you can keep is the longest prefix of the pattern that also appears as a suffix of p[0..j-1] — and that number is exactly lps[j-1]. So you set j = lps[j-1] and the already-matched suffix lines up with a prefix of the pattern automatically. The text pointer doesn't move.

Building LPS is KMP applied to the pattern against itself. Walk the pattern with two indices: i (current position) and len (length of the current longest prefix-suffix). If p[i] == p[len], extend: len++, lps[i] = len, advance i. If they differ and len > 0, fall back with len = lps[len-1] — and critically do not advance `i`, because you want to retry the new, shorter candidate at the same position. Only when len == 0 and characters still differ do you set lps[i] = 0 and advance i. Advancing i on the fall-back branch is the single most common bug in this build.

The search loop. Keep i over the text and j over the pattern. While t[i] == p[j], advance both. When j reaches m you've found a match ending at i-1, so record start i-m and set j = lps[j-1] to continue (this is what enables overlapping matches). On a mismatch with j > 0, fall back j = lps[j-1] without moving i. On a mismatch with j == 0, advance i. Because i only ever increases, the text is scanned exactly once — that is the O(n) guarantee.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "aabaaab", p = "aab"

Array state

k=0

"a": no proper prefix → 0

k ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[0, 4]

C · Code with teaching comments

solution.javaJava

KMP — LPS Failure Function (Optimal) — optimal

6 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class KMPSearch {
5
    private int[] buildLps(String p) {
6
        int m = p.length();
7
        int[] lps = new int[m];
8
        int len = 0;
9
        int i = 1;
10
        while (i < m) {
11
            if (p.charAt(i) == p.charAt(len)) {
12
                len++;
13
                lps[i] = len;
14
                // Only advance the text pointer when j is already 0 — i never moves
15
                // backward.
16
                i++;
17
            // Mismatch while building: fall back to lps[len-1] and DO NOT advance i —
18
            // retry the shorter prefix at the same position.
19
            } else if (len > 0) {
20
                // The fall-back recurrence. Forgetting to keep i fixed here is the
21
                // classic LPS bug.
22
                len = lps[len - 1];
23
            } else {
24
                lps[i] = 0;
25
                i++;
26
            }
27
        }
28
        return lps;
29
    }
30
 
31
    public List<Integer> search(String t, String p) {
32
        List<Integer> result = new ArrayList<>();
33
        int n = t.length(), m = p.length();
34
        int[] lps = buildLps(p);
35
        int i = 0, j = 0;
36
        while (i < n) {
37
            if (t.charAt(i) == p.charAt(j)) {
38
                i++;
39
                j++;
40
                // Whole pattern consumed — a match ends at i-1, so its start is i-m.
41
                if (j == m) {
42
                    result.add(i - m);
43
                    // Continue from the longest prefix-suffix instead of 0 — this is
44
                    // what reports overlapping matches.
45
                    j = lps[j - 1];
46
                }
47
            // Mismatch in the scan: slide the pattern via lps without touching i.
48
            } else if (j > 0) {
49
                j = lps[j - 1];
50
            } else {
51
                i++;
52
            }
53
        }
54
        return result;
55
    }
56
 
57
    public static void main(String[] args) {
58
        System.out.println(new KMPSearch().search("aabaaab", "aab"));
59
    }
60
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.60 lines

D · Why it works and complexityO(n + m) timeO(m) spaceOpen the invariant and proofExplore the proof

The failure function turns the pattern's self-similarity into a jump table. A mismatch is not a dead end — the matched prefix is itself a string whose longest prefix-that-is-also-a-suffix tells you the largest safe shift. Bonus: lps[m-1] equals the length of the longest prefix-suffix of the whole pattern, so m − lps[m-1] is the pattern's smallest repeating period.

ComplexityO(n + m) time, O(m) space — Building lps is O(m): the index i only increases, and each fall-back strictly decreases len, so the amortized work is linear. The search is O(n): i never decreases, and j only falls back as many times as it advanced. Total O(n + m), with O(m) space for the lps array.

E · Edge cases and pitfalls7t = "aaaa", p = "aa" — lps = [0,1]; after each match j = lps[1] = 1 keeps one char overlap → matches at 0,1,2.Explore edge cases

Edge cases handled

t = "aaaa", p = "aa"lps = [0,1]; after each match j = lps[1] = 1 keeps one char overlap → matches at 0,1,2.
t = "abc", p = "abcd"m > remaining text never completes; loop ends with empty result, no crash.
t = "aaaa", p = "a"m = 1, lps = [0]; every position is a match → [0,1,2,3].

Pitfalls

Advancing i on the LPS fall-back branch — corrupts the whole table.
Resetting j to 0 after a match instead of lps[j-1] — misses overlapping occurrences.
Moving the text pointer backward on a mismatch — you've reinvented the naive algorithm.
Confusing 'proper prefix that is a suffix' with 'repeated character' — they coincide only for runs of one letter.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.ArrayList; import java.util.List; public class KMPSearch { private int[] buildLps(String p) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.ArrayList;
import java.util.List;

public class KMPSearch {
    private int[] buildLps(String p) {
        int m = p.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        while (i < m) {
            if (p.charAt(i) == p.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
        return lps;
    }

public List<Integer> search(String t, String p) {
        List<Integer> result = new ArrayList<>();
        int n = t.length(), m = p.length();
        int[] lps = buildLps(p);
        int i = 0, j = 0;
        while (i < n) {
            if (t.charAt(i) == p.charAt(j)) {
                i++;
                j++;
                if (j == m) {
                    result.add(i - m);
                    j = lps[j - 1];
                }
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(new KMPSearch().search("aabaaab", "aab"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Advancing i on the LPS fall-back

When p[i] != p[len] and len > 0, you must retry the shorter prefix at the SAME i. Advancing i skips a position and produces a wrong table that breaks every later search.

Explore the code comparison

Don't write this

elif length > 0:
    length = lps[length - 1]
    i += 1  # WRONG: skips re-checking p[i] against the shorter prefix

Write this instead

elif length > 0:
    length = lps[length - 1]
    # i is intentionally NOT advanced here

Falling back to 0 instead of lps[j-1]

Resetting j to 0 on a mismatch throws away the matched prefix — that is exactly the naive O(n·m) behaviour wearing a KMP costume.

Explore the code comparison

Don't write this

} else if (j > 0) {
    j = 0;        // discards the partial match
    i++;
}

Write this instead

} else if (j > 0) {
    j = lps[j - 1];  // reuse the matched prefix; i stays put
}

Dropping overlapping matches after a hit

Setting j = 0 after j == m forces the next match to start fresh, so 'aa' in 'aaaa' reports only index 0. Use lps[j-1] to keep the overlap.

Explore the code comparison

Don't write this

if j == m:
    result.append(i - m)
    j = 0  # misses overlapping occurrences

Write this instead

if j == m:
    result.append(i - m)
    j = lps[j - 1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Prefix-function (failure-function) reuse on mismatch

Code pattern to memorize

build lps[] for pattern:
    len = 0; lps[0] = 0; i = 1
    while i < m:
        if p[i] == p[len]: len++; lps[i] = len; i++
        elif len > 0: len = lps[len-1]   # fall back, DON'T i++
        else: lps[i] = 0; i++

search:
    i = 0 (text), j = 0 (pattern)
    on match: i++, j++; if j == m -> hit at i-j, j = lps[j-1]
    on mismatch: if j > 0: j = lps[j-1] else i++

Rules to remember

1The text pointer i never moves backward — that single invariant is the whole O(n) guarantee.
2On a mismatch you fall back to lps[j-1], not to 0 and not to j-1. Resetting to 0 is the naive algorithm in disguise.
3lps[k] is the length of the longest proper prefix of p[0..k] that is also a suffix — proper means it can't be the whole substring.
4When building lps, on the fall-back branch you do not advance i. Advancing there is the #1 KMP build bug.
5After a full match, set j = lps[j-1] to keep finding overlapping occurrences instead of resetting to 0.

Use this pattern when

Find all occurrences of a pattern inside a longer text
Single pattern, many queries against the same pattern (build LPS once)
You need a guaranteed O(n + m) worst case, not just average
Detecting periodicity / smallest repeating unit (lps[m-1] gives it for free)

Choose another pattern when

Multiple patterns at once → Aho–Corasick, not one KMP per pattern
Approximate / fuzzy matching → edit-distance DP, not exact matching
Average-case is fine and hashing is simpler → Rabin–Karp rolling hash
You only need *whether* it exists once and strings are tiny → built-in indexOf is fine

Interview takeaway

KMP's one idea: when characters mismatch, the part of the pattern you already matched is itself a string whose prefix/suffix structure tells you how far you can safely jump. Precompute that structure once, then the text scan never backtracks.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPrefix-Function / Failure-Function reuse. Recognise it whenever exact matching or string self-similarity is involved: KMP search, smallest period, Z-algorithm cousins, and the trie-based Aho–Corasick all spring from the same 'remember the matched prefix' idea.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Shortest Palindrome (prepend to make palindrome)
Coming soon
Build LPS of p + '#' + reverse(p); lps of the combined string gives the longest palindromic prefix.
Repeated String Match
Coming soon
Use KMP to test whether b is a substring of repeated copies of a.
Find the Smallest Period of a String
Coming soon
If n % (n − lps[n-1]) == 0, the prefix of length n − lps[n-1] is the smallest repeating unit.
Aho–Corasick (multi-pattern search)
Coming soon
Generalizes KMP failure links to a trie of many patterns for simultaneous matching.

Same pattern

←

Longest Palindromic Substring — Manacher's Algorithm

Continue · Next problem

Pattern Search — Z-Algorithm

mediumStringsFrequently asked

Pattern Search — KMP (Knuth–Morris–Pratt)

Arrays & Hashing · 39 of 83 · 12 min

Given a text string t of length n and a pattern string p of length m, return all starting indices i (0-based) such that t[i..i+m-1] == p.

Occurrences may overlap (e.g. pattern aa in text aaaa occurs at indices 0, 1, 2). If the pattern never appears, return an empty list.

In plain English

Examples

Example 1

Input: t = "abxabcabcaby", p = "abcaby"
Output: [6]
Note: The pattern matches t[6..11] = "abcaby". The earlier "abc" runs are partial matches that KMP recovers from without rescanning the text.

Example 2

Input: t = "aaaa", p = "aa"
Output: [0, 1, 2]
Note: Overlapping matches. After a hit, j = lps[j-1] = 1 keeps one character of overlap instead of restarting.

Example 3

Input: t = "abcde", p = "fg"
Output: []
Note: No occurrence — the result is empty, not an error.

Constraints

1 ≤ m ≤ n ≤ 10⁶
Strings consist of printable ASCII characters
Overlapping occurrences must all be reported
An empty pattern is out of scope — assume m ≥ 1

Clarifying questions4First question: Do overlapping matches count as separate occurrences?Explore questions

Q1.Do overlapping matches count as separate occurrences?
Yes by default — `aa` in `aaaa` is three matches. Confirm this, because it changes whether you reset `j` to 0 or to `lps[j-1]` after a hit.
Q2.Are we matching a single pattern or many?
Single. If many patterns share one text, Aho–Corasick (a multi-pattern generalization of KMP) is the right tool.
Q3.Case-sensitive and full character set?
Assume case-sensitive ASCII unless told otherwise. KMP doesn't care about alphabet size — it compares characters directly.
Q4.Return indices or just a count / boolean?
Indices here. The algorithm is identical; you just collect instead of returning early.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand why naive matching is quadratic and can articulate the failure-function insight — that a partial match already encodes how much of the pattern is reusable.

Where candidates slip

Building the LPS array wrong: advancing the index on the fall-back branch, or confusing 'prefix that is also a suffix' with simple character repetition.

How to stand out

State the text-pointer-never-moves-back invariant explicitly, derive the LPS recurrence out loud, and mention that lps[m-1] reveals the pattern's smallest period.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive — Slide and Re-Compare	`O(n·m)`	`O(1)`	Open with this to anchor the complexity discussion — it makes the O(n + m) of KMP feel earned.	Read
2	KMP — LPS Failure Function (Optimal)Optimal	`O(n + m)`	`O(m)`	The answer they want. Lead with the invariant 'the text pointer never moves backward', then explain the LPS table that makes it possible.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive — Slide and Re-Compare

TimeO(n·m)SpaceO(1)

Open with this to anchor the complexity discussion — it makes the O(n + m) of KMP feel earned.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Try aligning the pattern at every possible start position s from 0 to n−m. For each start, compare characters until a mismatch or a full match.

2Hint 2Explore hint

What do you throw away when a mismatch happens at offset j? All j characters you just confirmed matched — you reset to start s+1 and begin again at j=0.

3Hint 3Explore hint

Count the worst case: text 'aaaa...a' with pattern 'aaa...ab'. Almost every alignment matches m−1 characters before failing on the last.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "abxabc", p = "abc"

Array state

s=0

matches ab, fails on x≠c

s ↓

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result[3]

C · Code with teaching comments

Reference implementation previewimport java.util.ArrayList; import java.util.List; public class NaiveSearch { public List<Integer> search(String t, String p) {Explore the full code

solution.javaJava

Naive — Slide and Re-Compare — reference

3 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class NaiveSearch {
5
    public List<Integer> search(String t, String p) {
6
        List<Integer> result = new ArrayList<>();
7
        int n = t.length(), m = p.length();
8
        // Try every alignment whose end stays inside the text — s ranges over n−m+1
9
        // positions.
10
        for (int s = 0; s + m <= n; s++) {
11
            int j = 0;
12
            // Compare from the pattern's start each time — this restart is the source
13
            // of the quadratic cost.
14
            while (j < m && t.charAt(s + j) == p.charAt(j)) {
15
                j++;
16
            }
17
            if (j == m) {
18
                result.add(s);
19
            }
20
        }
21
        return result;
22
    }
23
 
24
    public static void main(String[] args) {
25
        System.out.println(new NaiveSearch().search("abxabc", "abc"));
26
    }
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Looping s up to n instead of n−m → out-of-bounds reads near the end.Explore edge cases

Pitfalls

Looping s up to n instead of n−m → out-of-bounds reads near the end.
Claiming this is 'usually fine' — on adversarial inputs it is genuinely O(n·m).
Forgetting overlapping matches still work here only because you slide by exactly one.

03.2

Approach 2 of 2 · Optimal

KMP — LPS Failure Function (Optimal)

TimeO(n + m)SpaceO(m)

The answer they want. Lead with the invariant 'the text pointer never moves backward', then explain the LPS table that makes it possible.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Define lps[k] = length of the longest proper prefix of p[0..k] that is also a suffix. Precompute it for the whole pattern in O(m).

3Hint 3Explore hint

During the scan, on a mismatch set j = lps[j-1] (fall back within the pattern) and keep the text index i where it is. On a match advance both; on a full match record i−m and set j = lps[j-1].

A · Core idea

KMP runs in two phases: preprocess the pattern into an LPS array, then scan the text once.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

t = "aabaaab", p = "aab"

Array state

k=0

"a": no proper prefix → 0

k ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[0, 4]

C · Code with teaching comments

solution.javaJava

KMP — LPS Failure Function (Optimal) — optimal

6 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class KMPSearch {
5
    private int[] buildLps(String p) {
6
        int m = p.length();
7
        int[] lps = new int[m];
8
        int len = 0;
9
        int i = 1;
10
        while (i < m) {
11
            if (p.charAt(i) == p.charAt(len)) {
12
                len++;
13
                lps[i] = len;
14
                // Only advance the text pointer when j is already 0 — i never moves
15
                // backward.
16
                i++;
17
            // Mismatch while building: fall back to lps[len-1] and DO NOT advance i —
18
            // retry the shorter prefix at the same position.
19
            } else if (len > 0) {
20
                // The fall-back recurrence. Forgetting to keep i fixed here is the
21
                // classic LPS bug.
22
                len = lps[len - 1];
23
            } else {
24
                lps[i] = 0;
25
                i++;
26
            }
27
        }
28
        return lps;
29
    }
30
 
31
    public List<Integer> search(String t, String p) {
32
        List<Integer> result = new ArrayList<>();
33
        int n = t.length(), m = p.length();
34
        int[] lps = buildLps(p);
35
        int i = 0, j = 0;
36
        while (i < n) {
37
            if (t.charAt(i) == p.charAt(j)) {
38
                i++;
39
                j++;
40
                // Whole pattern consumed — a match ends at i-1, so its start is i-m.
41
                if (j == m) {
42
                    result.add(i - m);
43
                    // Continue from the longest prefix-suffix instead of 0 — this is
44
                    // what reports overlapping matches.
45
                    j = lps[j - 1];
46
                }
47
            // Mismatch in the scan: slide the pattern via lps without touching i.
48
            } else if (j > 0) {
49
                j = lps[j - 1];
50
            } else {
51
                i++;
52
            }
53
        }
54
        return result;
55
    }
56
 
57
    public static void main(String[] args) {
58
        System.out.println(new KMPSearch().search("aabaaab", "aab"));
59
    }
60
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.60 lines

D · Why it works and complexityO(n + m) timeO(m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7t = "aaaa", p = "aa" — lps = [0,1]; after each match j = lps[1] = 1 keeps one char overlap → matches at 0,1,2.Explore edge cases

Edge cases handled

t = "aaaa", p = "aa"lps = [0,1]; after each match j = lps[1] = 1 keeps one char overlap → matches at 0,1,2.
t = "abc", p = "abcd"m > remaining text never completes; loop ends with empty result, no crash.
t = "aaaa", p = "a"m = 1, lps = [0]; every position is a match → [0,1,2,3].

Pitfalls

Advancing i on the LPS fall-back branch — corrupts the whole table.
Resetting j to 0 after a match instead of lps[j-1] — misses overlapping occurrences.
Moving the text pointer backward on a mismatch — you've reinvented the naive algorithm.
Confusing 'proper prefix that is a suffix' with 'repeated character' — they coincide only for runs of one letter.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.ArrayList; import java.util.List; public class KMPSearch { private int[] buildLps(String p) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.ArrayList;
import java.util.List;

public static void main(String[] args) {
        System.out.println(new KMPSearch().search("aabaaab", "aab"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Advancing i on the LPS fall-back

When p[i] != p[len] and len > 0, you must retry the shorter prefix at the SAME i. Advancing i skips a position and produces a wrong table that breaks every later search.

Explore the code comparison

Don't write this

elif length > 0:
    length = lps[length - 1]
    i += 1  # WRONG: skips re-checking p[i] against the shorter prefix

Write this instead

elif length > 0:
    length = lps[length - 1]
    # i is intentionally NOT advanced here

Falling back to 0 instead of lps[j-1]

Resetting j to 0 on a mismatch throws away the matched prefix — that is exactly the naive O(n·m) behaviour wearing a KMP costume.

Explore the code comparison

Don't write this

} else if (j > 0) {
    j = 0;        // discards the partial match
    i++;
}

Write this instead

} else if (j > 0) {
    j = lps[j - 1];  // reuse the matched prefix; i stays put
}

Dropping overlapping matches after a hit

Setting j = 0 after j == m forces the next match to start fresh, so 'aa' in 'aaaa' reports only index 0. Use lps[j-1] to keep the overlap.

Explore the code comparison

Don't write this

if j == m:
    result.append(i - m)
    j = 0  # misses overlapping occurrences

Write this instead

if j == m:
    result.append(i - m)
    j = lps[j - 1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Prefix-function (failure-function) reuse on mismatch

Code pattern to memorize

build lps[] for pattern:
    len = 0; lps[0] = 0; i = 1
    while i < m:
        if p[i] == p[len]: len++; lps[i] = len; i++
        elif len > 0: len = lps[len-1]   # fall back, DON'T i++
        else: lps[i] = 0; i++

search:
    i = 0 (text), j = 0 (pattern)
    on match: i++, j++; if j == m -> hit at i-j, j = lps[j-1]
    on mismatch: if j > 0: j = lps[j-1] else i++

Rules to remember

1The text pointer i never moves backward — that single invariant is the whole O(n) guarantee.
2On a mismatch you fall back to lps[j-1], not to 0 and not to j-1. Resetting to 0 is the naive algorithm in disguise.
3lps[k] is the length of the longest proper prefix of p[0..k] that is also a suffix — proper means it can't be the whole substring.
4When building lps, on the fall-back branch you do not advance i. Advancing there is the #1 KMP build bug.
5After a full match, set j = lps[j-1] to keep finding overlapping occurrences instead of resetting to 0.

Use this pattern when

Find all occurrences of a pattern inside a longer text
Single pattern, many queries against the same pattern (build LPS once)
You need a guaranteed O(n + m) worst case, not just average
Detecting periodicity / smallest repeating unit (lps[m-1] gives it for free)

Choose another pattern when

Multiple patterns at once → Aho–Corasick, not one KMP per pattern
Approximate / fuzzy matching → edit-distance DP, not exact matching
Average-case is fine and hashing is simpler → Rabin–Karp rolling hash
You only need *whether* it exists once and strings are tiny → built-in indexOf is fine

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Shortest Palindrome (prepend to make palindrome)
Coming soon
Build LPS of p + '#' + reverse(p); lps of the combined string gives the longest palindromic prefix.
Repeated String Match
Coming soon
Use KMP to test whether b is a substring of repeated copies of a.
Find the Smallest Period of a String
Coming soon
If n % (n − lps[n-1]) == 0, the prefix of length n − lps[n-1] is the smallest repeating unit.
Aho–Corasick (multi-pattern search)
Coming soon
Generalizes KMP failure links to a trie of many patterns for simultaneous matching.

Same pattern

←

Longest Palindromic Substring — Manacher's Algorithm

Continue · Next problem

Pattern Search — Z-Algorithm