KMP (Knuth–Morris–Pratt) Algorithm

KMP finds a pattern in O(n + m) by never re-comparing matched characters — the LPS array says where to resume after a mismatch.

LPS[i] = length of the longest proper prefix of the pattern that is also a suffix of pattern[0..i].

Focus on recognizing:

“Find pattern” + “linear time required” → build LPS, then scan text once

Pattern 1: Build the LPS Array

Watch the LPS array fill for "ABABC" — matches extend j, mismatches fall back via lps[j-1]. Press ▶ to animate.

KMP (LPS Array)

Build the longest-prefix-suffix array for fast pattern matching.

lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix. On mismatch at j, fall back to lps[j-1] instead of restarting at 0 — the matched prefix is reused. O(m) to build, enabling O(n+m) search.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        lps[0] = 0; j = 0
                      
                        2
                        for i in 1..m-1:
                      
                        3
                          while j > 0 && p[i] != p[j]: j = lps[j-1]
                      
                        4
                          if p[i] == p[j]: j++
                      
                        5
                          lps[i] = j

private int[] buildLps(String p) {
    int m = p.length();
    int[] lps = new int[m];
    int j = 0;                       // current prefix length

    for (int i = 1; i < m; i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j))
            j = lps[j - 1];          // fall back

        if (p.charAt(i) == p.charAt(j))
            j++;

        lps[i] = j;
    }

    return lps;
}

def build_lps(p):
    m = len(p)
    lps = [0] * m
    j = 0                    # current prefix length

    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = lps[j - 1]   # fall back

        if p[i] == p[j]:
            j += 1

        lps[i] = j

    return lps

vector<int> buildLps(const string& p) {
    int m = p.size();
    vector<int> lps(m, 0);
    int j = 0;                   // current prefix length

    for (int i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j])
            j = lps[j - 1];      // fall back

        if (p[i] == p[j])
            j++;

        lps[i] = j;
    }

    return lps;
}

function buildLps(p) {
  const m = p.length;
  const lps = new Array(m).fill(0);
  let j = 0; // current prefix length

  for (let i = 1; i < m; i++) {
    while (j > 0 && p[i] !== p[j]) j = lps[j - 1]; // fall back

    if (p[i] === p[j]) j++;

    lps[i] = j;
  }

  return lps;
}

Match → j++. Mismatch → j = lps[j-1] until it fits. Never restart from zero.

Pattern 2: Search the Text

Same fallback logic while scanning the text:

public List<Integer> search(String text, String pat) {
    List<Integer> hits = new ArrayList<>();
    int[] lps = buildLps(pat);
    int j = 0;

    for (int i = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pat.charAt(j))
            j = lps[j - 1];

        if (text.charAt(i) == pat.charAt(j))
            j++;

        if (j == pat.length()) {     // full match
            hits.add(i - j + 1);
            j = lps[j - 1];          // keep scanning
        }
    }

    return hits;
}

def search(text, pat):
    lps = build_lps(pat)
    hits = []
    j = 0

    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = lps[j - 1]

        if ch == pat[j]:
            j += 1

        if j == len(pat):        # full match
            hits.append(i - j + 1)
            j = lps[j - 1]       # keep scanning

    return hits

vector<int> search(const string& text, const string& pat) {
    vector<int> lps = buildLps(pat), hits;
    int j = 0;

    for (int i = 0; i < (int)text.size(); i++) {
        while (j > 0 && text[i] != pat[j])
            j = lps[j - 1];

        if (text[i] == pat[j])
            j++;

        if (j == (int)pat.size()) {   // full match
            hits.push_back(i - j + 1);
            j = lps[j - 1];           // keep scanning
        }
    }

    return hits;
}

function search(text, pat) {
  const lps = buildLps(pat);
  const hits = [];
  let j = 0;

  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pat[j]) j = lps[j - 1];

    if (text[i] === pat[j]) j++;

    if (j === pat.length) {
      // full match
      hits.push(i - j + 1);
      j = lps[j - 1]; // keep scanning
    }
  }

  return hits;
}

After a hit, reset with j = lps[j-1] — overlapping matches are found too.

Pattern 3: Repeated Substring Pattern

s is made of a repeated block iff n % (n - lps[n-1]) == 0 and lps[n-1] > 0:

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    int len = buildLps(s)[n - 1];

    return len > 0 && n % (n - len) == 0;
}

def repeated_substring_pattern(s):
    n = len(s)
    longest = build_lps(s)[-1]

    return longest > 0 and n % (n - longest) == 0

bool repeatedSubstringPattern(string s) {
    int n = s.size();
    int longest = buildLps(s)[n - 1];

    return longest > 0 && n % (n - longest) == 0;
}

function repeatedSubstringPattern(s) {
  const n = s.length;
  const longest = buildLps(s)[n - 1];

  return longest > 0 && n % (n - longest) === 0;
}

n − lps[n−1] is the candidate period; divisibility confirms it tiles the whole string.

Common Mistakes

Starting LPS at index 0.

lps[0] is always 0 — a proper prefix can’t be the whole string.

Resetting j = 0 after a full match.

Use lps[j-1], or you miss overlapping occurrences like "aa" in "aaaa".

Forgetting the fallback loop.

A single if instead of while breaks on patterns like "aabaaac".

Complexity

Step	Time	Space
Build LPS	O(m)	O(m)
Search	O(n)	O(1) extra

⚠️ Animation & Content Notice

Pattern 1: Build the LPS Array

⚠️ Animation & Content Notice

KMP (LPS Array)

Pattern 2: Search the Text

Pattern 3: Repeated Substring Pattern

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern 1: Build the LPS Array

KMP (LPS Array)

Pattern 2: Search the Text

Pattern 3: Repeated Substring Pattern

Common Mistakes

Complexity

Premium Content

My Private Notes