On this page

KMP & the Prefix Function

Why this exists

You are reading a long novel, looking for the phrase "abab c abab" (spaces added only so you can read it). You read along, and for a while it goes well: a, b, a, b... then the next letter is wrong. A naive reader now does something silly. They go back to the second letter of where they started and begin again from scratch, re-reading letters they have already seen. A smart reader thinks: "Wait. The last two letters I read were a b. That is also how my phrase starts. So I am not back at zero. I am already two letters into a new attempt."

That thought is the whole of the Knuth–Morris–Pratt algorithm (KMP). It finds every place a short string (the pattern, length ) appears inside a long string (the text, length ) in time. It never moves backwards in the text. It reads each text character once, so it can run on a stream that you cannot rewind: a network socket, a log being written, a DNA sequencer's output.

The trick is a small table computed from the pattern alone, called the prefix function (also called the failure function, or the "partial match table"). For each position in the pattern it answers one question:

If I have matched this much of the pattern and the next character fails, how much of what I matched can I reuse?

The String Algorithms overview showed KMP in a few lines. This lesson builds the prefix function slowly, by hand, on the string ababcabab; traces the search step by step; proves it correct; explains in plain words why it is linear; and then uses the same table for three more jobs: finding the period of a string, counting occurrences of every prefix, and building the KMP automaton, a tiny machine that powers "count strings that avoid a pattern" dynamic programming.

The history is short. James H. Morris and Vaughan Pratt found the linear-time algorithm in 1970. Donald Knuth found it independently (from automata theory) and improved the failure table. The three published it together in 1977 ("Fast pattern matching in strings", SIAM Journal on Computing 6(2)).

Pattern triggers

If the problem says or has…Think of…
"find all occurrences of P in T", lengths up to , overlaps allowedKMP search (or the Z-algorithm)
"longest prefix that is also a suffix", "border", "happy prefix"The last value of the prefix function
"is the string a repetition of a smaller block", "smallest period", "string compression by repetition"Period
"all borders", "all periods"Walk the chain
"how many times does each prefix occur"Count prefix-function values, then push counts down the chain
"shortest palindrome by adding characters in front"Prefix function of s + '#' + reverse(s)
"is B a rotation of A"Search B in A + A
"merge words removing the overlap"Prefix function of next + '#' + tail of current
"count strings of length N that do not contain P"DP over the KMP automaton states
Streaming input, cannot buffer or rewindKMP: one forward pass, state is a single integer
Many patterns at onceNot KMP: Aho–Corasick, which is KMP on a trie

The meta-trigger: the answer depends on how a string overlaps with itself. Whenever a prefix of something lines up with a suffix of something, the prefix function is the natural tool.

Intuition & first principles

The waste in naive matching

Naive matching tries every start position and compares the pattern to the text from that position until a mismatch. Take pattern ababcabab and the 16-character text abababcababcabab:

text:     a b a b a b c a b a b c a b a b
start 0:  a b a b c          <- 4 matches, then 'a' vs 'c' fails
start 1:    a                <- 'b' vs 'a' fails
start 2:      a b a b c a b a b    <- full match
...

At start 0 we learned four text letters: a b a b. Then we threw that knowledge away and restarted at start 1, re-comparing letters we had already seen. In the worst case (text aaaa…a, pattern aaaaaaaaab) every start position re-reads characters. Measured on a 1,000-letter text of all as with the 10-letter pattern aaaaaaaaab, naive matching makes 9,910 character comparisons. KMP makes 1,991. The gap grows with : naive is in the worst case, KMP is at most comparisons in the search, whatever the pattern.

What can we reuse?

Go back to start 0. We had matched abab (4 letters) and then the text said a where the pattern wanted c. Where could the pattern possibly start next?

A new attempt starting at text position must agree with the text letters we already know. Those letters are the matched part, abab. So the new attempt, slid to the right, must have its beginning sitting on the end of abab. Concretely, we need a string that is both:

  • a prefix of abab (because a new attempt starts with the pattern's first letters), and
  • a suffix of abab (because it lines up with the most recent text letters).

abab has two candidates: ab (prefix ab…, suffix …ab) and the empty string. The longest is ab. So without looking at the text again, we know the next possible match starts with ab already matched. We set "matched so far" from 4 to 2 and compare the same text letter a against the pattern's third letter a. It matches. We lost nothing and re-read nothing.

That is the answer to "how much of what I matched can I reuse": the longest proper prefix of the matched part that is also its suffix.

Vocabulary

  • A prefix of a string is a piece taken from its start: prefixes of abc are "", a, ab, abc.
  • A suffix is a piece taken from its end: "", c, bc, abc.
  • Proper means "not the whole string". We need proper ones, because "reuse the whole match" would mean not sliding at all.
  • A border of a string is a proper prefix that is also a suffix. abab has borders ab and "". aaaa has borders aaa, aa, a, "". abcd has only "".
  • The prefix function of a string is the array where is the length of the longest border of (the prefix ending at position ). By definition .

So the prefix function is a list of "how much can I reuse" answers, one for each possible amount matched.

The one-sentence summary

After matching pattern characters and failing on the next one, KMP sets and tries the same text character again. If that fails too, it repeats. The text pointer never moves back.

The decision at every text character

flowchart TD
    A["Read next text char c, j = chars matched"] --> B{"c equals pattern[j]?"}
    B -- yes --> C["j = j + 1"]
    B -- no --> D{"j > 0?"}
    D -- yes --> E["j = pi[j-1], reuse a shorter border"]
    E --> B
    D -- no --> F["j stays 0, move on"]
    C --> G{"j equals m?"}
    G -- yes --> H["Report match, j = pi[m-1]"]
    G -- no --> I["Next text char"]
    H --> I
    F --> I

Why "a border of a border"

When the reuse fails too, what next? Suppose we had matched abab, fell back to the border ab, and the next letter still does not fit. We now need the next shorter border of abab. Here is the key fact: every border of a string, other than the longest, is a border of the longest border. A border of abab that is shorter than ab must be a prefix of ab (it is a prefix of abab and shorter than ab) and a suffix of ab (it is a suffix of abab, and ab is the end of abab). So it is a border of ab, and the longest one has length .

So the borders of , from longest to shortest, are found by following a chain:

For ababcabab (whole string, ) the chain is : borders abab, ab, "".

flowchart LR
    W["ababcabab"] -- "longest border" --> B4["abab (pi[8] = 4)"]
    B4 -- "its longest border" --> B2["ab (pi[3] = 2)"]
    B2 -- "its longest border" --> B0["empty (pi[1] = 0)"]

The table therefore stores every border of every prefix, in compressed form: one number per position, and the rest is reached by hopping.

Mechanics

The prefix function, built by hand on ababcabab

We fill left to right. The rule that makes it fast: to get , try to extend a border of by one character. A border of of length is a border of of length , plus the character , which must equal the character just after that border, . So:

  1. Start with , the longest border of the previous prefix.
  2. If , the border grows: .
  3. If not, and , try the next shorter border: , go to 2.
  4. If and , then .

Notice this is the search algorithm run on the pattern against itself. Let's do it at the whiteboard. The string, with indices:

index012345678
charababcabab
  • . a alone has no proper prefix except "". .
  • (ab). . Compare = b with = a: different, and is already 0. . Indeed ab starts with a and ends with b.
  • (aba). . Compare = a with = a: equal. . Border a.
  • (abab). . We have the border a; can it grow to ab? Compare = b with = b: equal. . Border ab.
  • (ababc). . Try to grow ab into aba… compare = c with = a: different. Fall back: . Compare = c with = a: different, . . No border can end in c, because c never appears at the front.
  • (ababca). . a vs = a: equal. .
  • (ababcab). . b vs = b: equal. .
  • (ababcaba). . a vs = a: equal. .
  • (ababcabab). . b vs = b: equal. . The whole string ends with abab, which is also how it starts.

Trace table

One row per position. "Comparisons" lists each vs test in order, with fallbacks in between. This table was checked by running the generator scripts/traces/kmp_prefix_function.py, the same run the visualizer below plays back.

at start ()Comparisons and fallbacksBorder
0a——0""
1b0b vs s[0]=a ✗0""
2a0a vs s[0]=a ✓1a
3b1b vs s[1]=b ✓2ab
4c2c vs s[2]=a ✗ → ; c vs s[0]=a ✗0""
5a0a vs s[0]=a ✓1a
6b1b vs s[1]=b ✓2ab
7a2a vs s[2]=a ✓3aba
8b3b vs s[3]=b ✓4abab

Result:

Two things to notice. First, climbs by at most 1 per step (from 0 to 1 to 2) and then can crash down (from 2 to 0 at the c). It never jumps up by 2. Second, there were only 10 comparisons for 8 positions. That is not a coincidence; it is the amortised bound proved below.

The prefix function is the pattern matched against itself: a match grows the border by one, a mismatch falls back to the next shorter border, k = π[k − 1].

In the visualizer, the shaded window is the border being extended (a suffix of what we have seen), the cyan cell is , the character that must match, and the amber cell is .

The matching phase

Now use the table. The variable means "how many pattern characters currently match, ending at the text character just read". The code is the same loop as the prefix function:

KMP-SEARCH(T, P):
    pi = PREFIX-FUNCTION(P);  j = 0
    for i = 0 .. n-1:
        while j > 0 and T[i] != P[j]:
            j = pi[j-1]            # reuse the longest border of P[0..j-1]
        if T[i] == P[j]:
            j = j + 1
        if j == m:
            report match at i - m + 1
            j = pi[m-1]            # keep going, overlaps allowed

After a full match we do not reset to 0. The matched text is the whole pattern, and its longest border can start the next occurrence. That is how KMP finds overlapping matches, like aa at positions 0, 1, 2, 3 in aaaaa.

Trace: searching ababcabab in abababcababcabab

Pattern = ababcabab with . Text (16 letters):

index0123456789101112131415
charabababcababcabab

Here is the run, produced by scripts/traces/kmp_search.py:

beforeFallbacksCompare afterEvent
0a0—P[0]=a ✓1
1b1—P[1]=b ✓2
2a2—P[2]=a ✓3
3b3—P[3]=b ✓4matched abab
4a4P[4]=c ✗ → P[2]=a ✓3reused ab
5b3—P[3]=b ✓4
6c4—P[4]=c ✓5
7a5—P[5]=a ✓6
8b6—P[6]=b ✓7
9a7—P[7]=a ✓8
10b8—P[8]=b ✓9match at 2, then
11c4—P[4]=c ✓5reused abab
12a5—P[5]=a ✓6
13b6—P[6]=b ✓7
14a7—P[7]=a ✓8
15b8—P[8]=b ✓9match at 7, then

Matches at 2 and 7. They overlap: the first occupies 2..10 and the second 7..15, sharing abab at 7..10. Look at row 4: the naive method would restart at text position 1 and re-read. KMP keeps and only changes . Look at row 10: after the match KMP already knows the next attempt starts with abab matched, because . Over the whole run it made 17 character comparisons; naive matching on the same input makes 30.

The shaded window is the part of the text currently matched (its length is ); start marks where the current attempt begins. Watch start jump forward on a fallback while i stands still.

The separator trick

There is an even shorter way to search: compute the prefix function of the single string

where # is a character that occurs in neither string. Every border of a prefix of has length at most , because a border longer than would contain # at its start side but not at the same position on its end side. So exactly when the characters ending at position equal , which is an occurrence ending at text index . One function, no separate search loop. It costs memory instead of , which is the price. The same separator idea drives the Z-algorithm's matching (P + '$' + T) in the next lesson.

The ladder: brute force → better → optimal

Problem: report every occurrence of (length ) in (length ).

Rung 1: naive sliding

Try every start; compare until mismatch. worst case, extra space. Fast in practice on random English text, because most attempts fail on the first or second letter. Terrible on repetitive inputs (DNA, aaaa…, binary data, adversarial tests).

Rung 2: hashing (Rabin–Karp)

Compare a rolling hash of each window with the pattern's hash, and verify on equal hashes. expected; worst case if you verify every candidate and an adversary forces many collisions; no false positives if you verify. Great for many patterns of the same length and for substring-equality questions. See String Hashing.

Rung 3: KMP

to build , to search, deterministic, extra space, one forward pass over the text. Optimal up to constants: any correct algorithm must, in the worst case, look at every text character.

Rung 3': Z-algorithm

Same , a different table ( = longest common prefix of and ). Equivalent power; some people find it easier to write. Not naturally streaming, because it works on P + '$' + T as a whole.

Rung 4 (practice, not worst case): Boyer–Moore family and Two-Way

Boyer–Moore compares from the right end of the pattern and can skip up to characters per mismatch, so on natural text it reads only a fraction of the input (sublinear on average). Two-Way (Crochemore and Perrin, 1991) gives worst case with extra space. Standard libraries tend to use these, not KMP (see Real-world uses).

RungMethodWorst timeTypical timeExtra spaceStreaming?Why it improves
1Naive on random textneeds -bufferBaseline
2Rabin–Karp with verification, expectedyesCompares windows in
3KMPyes, no bufferNever re-reads the text
3'Z-algorithmnoSame, via common prefixes
4Boyer–Moore / Two-Way with Galil's rule / Two-Waysublinear on text / noSkips characters

Correctness

Plain-words proofs. Write for the prefix ending at , and "border" for a proper prefix that is also a suffix.

Lemma 1 (borders of borders)

If is the longest border of , then the borders of are exactly and the borders of .

Why. A border of is a prefix of , hence of ; and a suffix of , hence of (since is a suffix of ). So it is a border of . Conversely, a border of shorter than is a prefix of shorter than , so a prefix of ; it is a suffix of shorter than , so a suffix of . So is a border of .

Consequence: the borders of , longest first, have lengths . The fallback visits them in order and skips none.

Lemma 2 (the prefix function grows by at most one)

.

Why. Take the longest border of , of length . Chop its last character off on both sides: what is left, of length , is a prefix of and a suffix of , so a border of . So .

Theorem (the construction computes )

Any border of of length is (a border of of length ) followed by , and that requires . So is for the largest border length of with , or 0 if there is none. By Lemma 1, the loop tries the border lengths of in decreasing order, starting from , and stops at the first that works. The first that works is the largest. If it reaches and , no border extends, and .

Theorem (the search finds every occurrence)

Invariant: after processing , is the length of the longest prefix of that is a suffix of (capped below after reporting a match, by the reset to ).

Why it holds. Before reading , is the longest prefix of ending at . Any prefix of ending at , of length , is a prefix of of length ending at plus a matching character. The prefixes of ending at are and, by Lemma 1, its borders, reached by the fallback chain in decreasing order. The loop stops at the longest one that extends, exactly as in the construction. After a full match, the occurrences that might still be in progress are the borders of , the longest of which is .

Why no occurrence is missed. An occurrence of ending at is a prefix of of length ending at . The longest such prefix is then (it cannot be longer), so after processing and it is reported. And every report is real, since means the last text characters equal .

The proof never says "slide by this many and hope". KMP only discards start positions that cannot match, because a start that could match would correspond to a border that the chain visits.

Complexity

The amortised argument, in plain words

The while loop looks dangerous. A single character can trigger many fallbacks. Pattern aaaa, text aaab: at the b, falls . Could that happen at every character, making KMP ?

No. Think of as the height of a person on a staircase:

  • Each text character can raise by at most one step (the j += 1).
  • Each fallback lowers by at least one step (, since a border is shorter than the string).
  • can never go below the ground floor, 0.

You cannot walk down more steps than you have walked up. Over the whole search, goes up at most times in total, so it can go down at most times in total. Some characters cause many fallbacks, but they can only spend height that earlier characters built up. Adding it all up:

  • j += 1 happens at most times,
  • fallbacks happen at most times in total,
  • so there are at most character comparisons (each loop iteration does one comparison, plus one comparison per character for the final if).

That is what amortised means: one step may be expensive, but the total over all steps is small, so the average per step is constant. Accountants would call it a bank balance: each character deposits at most one coin, each fallback withdraws at least one, and the balance never goes negative.

The same argument applies to building , with in place of : at most increases, so at most fallbacks, total. (The resets after a match in the search lower , which only helps.)

So:

PhaseTimeSpace
Prefix function, at most comparisons
Search, at most comparisons beyond
Total

Measured: on 1,000 as with pattern aaaaaaaaab, 1,991 comparisons (); naive needs 9,910.

Best and worst. Best case is about comparisons (no fallbacks). Worst case is about . There is no input that makes KMP slower than linear; that is the point of choosing it.

Delay. The total is linear, but the time spent on one text character (the delay) can be up to fallbacks with the plain prefix function (the aaab example). Knuth's strict version of the table (see Variations) cuts the worst delay to ; Galil (1981) gave a real-time variant with constant work per character. This matters only for hard real-time systems.

Implementation

Prefix function, search (overlapping matches), smallest period, occurrences of every prefix, and the KMP automaton, with the same assertions in every language. Every snippet was compiled and run (Python 3.12, Java 24, g++ 6.3 with -std=c++14 -O2, TypeScript 5.8 with tsc --strict and tsx).

def prefix_function(s: str) -> list[int]:
    """pi[i] = length of the longest proper prefix of s[:i+1] that is also its suffix."""
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        k = pi[i - 1]                    # longest border we can try to extend
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]                # fall back to the next shorter border
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi


def kmp_search(text: str, pattern: str) -> list[int]:
    """Start indices of every (possibly overlapping) occurrence of pattern in text."""
    m = len(pattern)
    if m == 0:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    found = []
    j = 0                                # characters of pattern matched so far
    for i, c in enumerate(text):
        while j > 0 and c != pattern[j]:
            j = pi[j - 1]
        if c == pattern[j]:
            j += 1
        if j == m:
            found.append(i - m + 1)
            j = pi[j - 1]                # reuse the border; allows overlaps
    return found


def smallest_period(s: str) -> int:
    """Smallest p > 0 with s[i] == s[i + p] for all valid i."""
    return len(s) - prefix_function(s)[-1] if s else 0


def prefix_occurrences(s: str) -> list[int]:
    """ans[k - 1] = number of occurrences of the prefix s[:k] inside s."""
    n = len(s)
    pi = prefix_function(s)
    cnt = [0] * (n + 1)
    for v in pi:
        cnt[v] += 1                      # position i ends a copy of prefix pi[i]
    for k in range(n, 0, -1):
        cnt[pi[k - 1]] += cnt[k]         # a copy of prefix k contains a copy of its border
    return [cnt[k] + 1 for k in range(1, n + 1)]   # +1: the prefix itself


def kmp_automaton(pattern: str, alphabet: str) -> list[list[int]]:
    """delta[q][c] = matched length after reading alphabet[c] in state q."""
    m = len(pattern)
    pi = prefix_function(pattern)
    delta = [[0] * len(alphabet) for _ in range(m + 1)]
    for q in range(m + 1):
        for ci, c in enumerate(alphabet):
            if q < m and pattern[q] == c:
                delta[q][ci] = q + 1
            elif q > 0:
                delta[q][ci] = delta[pi[q - 1]][ci]
    return delta


if __name__ == "__main__":
    assert prefix_function("ababcabab") == [0, 0, 1, 2, 0, 1, 2, 3, 4]
    assert prefix_function("aabaaab") == [0, 1, 0, 1, 2, 2, 3]
    assert kmp_search("abababcababcabab", "ababcabab") == [2, 7]
    assert kmp_search("ABABDABACDABABCABAB", "ABABCABAB") == [10]
    assert kmp_search("aaaaa", "aa") == [0, 1, 2, 3]
    assert kmp_search("abc", "abcd") == []
    assert smallest_period("abcabcab") == 3
    assert smallest_period("abababab") == 2
    assert prefix_occurrences("ababcabab") == [4, 4, 2, 2, 1, 1, 1, 1, 1]
    assert kmp_automaton("abab", "ab") == [[1, 0], [1, 2], [3, 0], [1, 4], [3, 0]]
    print("python ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Kmp {
    /** pi[i] = length of the longest proper prefix of s[0..i] that is also its suffix. */
    static int[] prefixFunction(String s) {
        int n = s.length();
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int k = pi[i - 1];                       // longest border we can try to extend
            while (k > 0 && s.charAt(i) != s.charAt(k)) {
                k = pi[k - 1];                       // fall back to the next shorter border
            }
            if (s.charAt(i) == s.charAt(k)) k++;
            pi[i] = k;
        }
        return pi;
    }

    /** Start indices of every (possibly overlapping) occurrence of pattern in text. */
    static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> found = new ArrayList<>();
        int m = pattern.length();
        if (m == 0) {
            for (int i = 0; i <= text.length(); i++) found.add(i);
            return found;
        }
        int[] pi = prefixFunction(pattern);
        int j = 0;                                   // characters of pattern matched so far
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            while (j > 0 && c != pattern.charAt(j)) j = pi[j - 1];
            if (c == pattern.charAt(j)) j++;
            if (j == m) {
                found.add(i - m + 1);
                j = pi[j - 1];                       // reuse the border; allows overlaps
            }
        }
        return found;
    }

    /** Smallest p > 0 with s[i] == s[i + p] for all valid i. */
    static int smallestPeriod(String s) {
        return s.isEmpty() ? 0 : s.length() - prefixFunction(s)[s.length() - 1];
    }

    /** result[k - 1] = number of occurrences of the prefix s[0..k) inside s. */
    static int[] prefixOccurrences(String s) {
        int n = s.length();
        int[] pi = prefixFunction(s);
        int[] cnt = new int[n + 1];
        for (int v : pi) cnt[v]++;                   // position i ends a copy of prefix pi[i]
        for (int k = n; k >= 1; k--) cnt[pi[k - 1]] += cnt[k];
        int[] ans = new int[n];
        for (int k = 1; k <= n; k++) ans[k - 1] = cnt[k] + 1;   // +1: the prefix itself
        return ans;
    }

    /** delta[q][c] = matched length after reading alphabet.charAt(c) in state q. */
    static int[][] kmpAutomaton(String pattern, String alphabet) {
        int m = pattern.length();
        int[] pi = prefixFunction(pattern);
        int[][] delta = new int[m + 1][alphabet.length()];
        for (int q = 0; q <= m; q++) {
            for (int c = 0; c < alphabet.length(); c++) {
                if (q < m && pattern.charAt(q) == alphabet.charAt(c)) delta[q][c] = q + 1;
                else if (q > 0) delta[q][c] = delta[pi[q - 1]][c];
            }
        }
        return delta;
    }

    public static void main(String[] args) {
        check(Arrays.equals(prefixFunction("ababcabab"), new int[]{0, 0, 1, 2, 0, 1, 2, 3, 4}));
        check(Arrays.equals(prefixFunction("aabaaab"), new int[]{0, 1, 0, 1, 2, 2, 3}));
        check(kmpSearch("abababcababcabab", "ababcabab").equals(List.of(2, 7)));
        check(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB").equals(List.of(10)));
        check(kmpSearch("aaaaa", "aa").equals(List.of(0, 1, 2, 3)));
        check(kmpSearch("abc", "abcd").isEmpty());
        check(smallestPeriod("abcabcab") == 3 && smallestPeriod("abababab") == 2);
        check(Arrays.equals(prefixOccurrences("ababcabab"), new int[]{4, 4, 2, 2, 1, 1, 1, 1, 1}));
        check(Arrays.deepEquals(kmpAutomaton("abab", "ab"), new int[][]{{1, 0}, {1, 2}, {3, 0}, {1, 4}, {3, 0}}));
        System.out.println("java ok");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// pi[i] = length of the longest proper prefix of s[0..i] that is also its suffix.
vector<int> prefixFunction(const string& s) {
    int n = (int)s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];                        // longest border we can try to extend
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // next shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

// Start indices of every (possibly overlapping) occurrence of pattern in text.
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> found;
    int m = (int)pattern.size();
    if (m == 0) {
        for (int i = 0; i <= (int)text.size(); i++) found.push_back(i);
        return found;
    }
    vector<int> pi = prefixFunction(pattern);
    int j = 0;                                    // characters of pattern matched so far
    for (int i = 0; i < (int)text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
        if (text[i] == pattern[j]) j++;
        if (j == m) {
            found.push_back(i - m + 1);
            j = pi[j - 1];                        // reuse the border; allows overlaps
        }
    }
    return found;
}

// Smallest p > 0 with s[i] == s[i + p] for all valid i.
int smallestPeriod(const string& s) {
    return s.empty() ? 0 : (int)s.size() - prefixFunction(s).back();
}

// result[k - 1] = number of occurrences of the prefix s[0..k) inside s.
vector<int> prefixOccurrences(const string& s) {
    int n = (int)s.size();
    vector<int> pi = prefixFunction(s), cnt(n + 1, 0), ans(n);
    for (int v : pi) cnt[v]++;                    // position i ends a copy of prefix pi[i]
    for (int k = n; k >= 1; k--) cnt[pi[k - 1]] += cnt[k];
    for (int k = 1; k <= n; k++) ans[k - 1] = cnt[k] + 1;   // +1: the prefix itself
    return ans;
}

// delta[q][c] = matched length after reading alphabet[c] in state q.
vector<vector<int> > kmpAutomaton(const string& pattern, const string& alphabet) {
    int m = (int)pattern.size(), a = (int)alphabet.size();
    vector<int> pi = prefixFunction(pattern);
    vector<vector<int> > delta(m + 1, vector<int>(a, 0));
    for (int q = 0; q <= m; q++)
        for (int c = 0; c < a; c++) {
            if (q < m && pattern[q] == alphabet[c]) delta[q][c] = q + 1;
            else if (q > 0) delta[q][c] = delta[pi[q - 1]][c];
        }
    return delta;
}

int main() {
    assert(prefixFunction("ababcabab") == vector<int>({0, 0, 1, 2, 0, 1, 2, 3, 4}));
    assert(prefixFunction("aabaaab") == vector<int>({0, 1, 0, 1, 2, 2, 3}));
    assert(kmpSearch("abababcababcabab", "ababcabab") == vector<int>({2, 7}));
    assert(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB") == vector<int>({10}));
    assert(kmpSearch("aaaaa", "aa") == vector<int>({0, 1, 2, 3}));
    assert(kmpSearch("abc", "abcd").empty());
    assert(smallestPeriod("abcabcab") == 3 && smallestPeriod("abababab") == 2);
    assert(prefixOccurrences("ababcabab") == vector<int>({4, 4, 2, 2, 1, 1, 1, 1, 1}));
    vector<vector<int> > want = {{1, 0}, {1, 2}, {3, 0}, {1, 4}, {3, 0}};
    assert(kmpAutomaton("abab", "ab") == want);
    cout << "c++ ok" << endl;
    return 0;
}
/** pi[i] = length of the longest proper prefix of s[0..i] that is also its suffix. */
function prefixFunction(s: string): number[] {
  const n = s.length;
  const pi: number[] = new Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    let k = pi[i - 1]; // longest border we can try to extend
    while (k > 0 && s[i] !== s[k]) k = pi[k - 1]; // next shorter border
    if (s[i] === s[k]) k++;
    pi[i] = k;
  }
  return pi;
}

/** Start indices of every (possibly overlapping) occurrence of pattern in text. */
function kmpSearch(text: string, pattern: string): number[] {
  const m = pattern.length;
  if (m === 0) return Array.from({ length: text.length + 1 }, (_, i) => i);
  const pi = prefixFunction(pattern);
  const found: number[] = [];
  let j = 0; // characters of pattern matched so far
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = pi[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === m) {
      found.push(i - m + 1);
      j = pi[j - 1]; // reuse the border; allows overlaps
    }
  }
  return found;
}

/** Smallest p > 0 with s[i] === s[i + p] for all valid i. */
function smallestPeriod(s: string): number {
  return s.length === 0 ? 0 : s.length - prefixFunction(s)[s.length - 1];
}

/** result[k - 1] = number of occurrences of the prefix s[0..k) inside s. */
function prefixOccurrences(s: string): number[] {
  const n = s.length;
  const pi = prefixFunction(s);
  const cnt: number[] = new Array(n + 1).fill(0);
  for (const v of pi) cnt[v]++; // position i ends a copy of prefix pi[i]
  for (let k = n; k >= 1; k--) cnt[pi[k - 1]] += cnt[k];
  return Array.from({ length: n }, (_, i) => cnt[i + 1] + 1); // +1: the prefix itself
}

/** delta[q][c] = matched length after reading alphabet[c] in state q. */
function kmpAutomaton(pattern: string, alphabet: string): number[][] {
  const m = pattern.length;
  const pi = prefixFunction(pattern);
  const delta: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(alphabet.length).fill(0));
  for (let q = 0; q <= m; q++) {
    for (let c = 0; c < alphabet.length; c++) {
      if (q < m && pattern[q] === alphabet[c]) delta[q][c] = q + 1;
      else if (q > 0) delta[q][c] = delta[pi[q - 1]][c];
    }
  }
  return delta;
}

function check(ok: boolean, what: string): void {
  if (!ok) throw new Error(what);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
check(same(prefixFunction("ababcabab"), [0, 0, 1, 2, 0, 1, 2, 3, 4]), "pi");
check(same(prefixFunction("aabaaab"), [0, 1, 0, 1, 2, 2, 3]), "pi2");
check(same(kmpSearch("abababcababcabab", "ababcabab"), [2, 7]), "search");
check(same(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"), [10]), "search2");
check(same(kmpSearch("aaaaa", "aa"), [0, 1, 2, 3]), "overlap");
check(kmpSearch("abc", "abcd").length === 0, "longer pattern");
check(smallestPeriod("abcabcab") === 3 && smallestPeriod("abababab") === 2, "period");
check(same(prefixOccurrences("ababcabab"), [4, 4, 2, 2, 1, 1, 1, 1, 1]), "occurrences");
check(same(kmpAutomaton("abab", "ab"), [[1, 0], [1, 2], [3, 0], [1, 4], [3, 0]]), "automaton");
console.log("ts ok");

Notes on the code:

  • Empty pattern. By convention the empty string occurs at every position (that is what Python's str.find and Java's indexOf assume). The functions return that list instead of indexing pattern[0] on an empty string.
  • Characters vs code points. Java charAt and TypeScript indexing work on UTF-16 code units, C++ on bytes. For ASCII this is invisible. For general Unicode, match on code points (or on normalized text), or both sides agree on encoding and you match bytes, which is still correct for exact matching of UTF-8.
  • No recursion, no hashing. Everything is integer arrays and comparisons; the code is deterministic and fast in every language.

Applications

1. The period of a string

A period of is a shift such that wherever both exist. abcabcab has period 3: shift it by 3 and it lines up with itself.

Borders and periods are the same thing seen from two sides. If has a border of length , then the first characters equal the last characters, which says for all . So is a period. And the argument runs backwards too. Hence:

smallest period ?Meaning
abcabcab0 0 0 1 2 3 4 553no (8 mod 3 = 2)abc repeated, cut short
abababab0 0 1 2 3 4 5 662yesab × 4
aabaab0 1 0 1 2 333yesaab × 2
aaaa0 1 2 331yesa × 4
abcd0 0 0 004yes (trivially)no repetition

Is a whole number of copies of a shorter block? Yes exactly when and , where is the smallest period. (If does not divide , no other period that divides can exist except itself. This follows from the Fine–Wilf periodicity lemma: if and are periods and , then is a period too. So a dividing period would force to be a period, contradicting minimality.) This is LeetCode 459 in one line.

Deeper: the Fine–Wilf lemma, in a sentence

Two periods and that "overlap enough" (the string has length at least ) generate a third period, , like the Euclidean algorithm run on shifts. It is the main tool for reasoning about repetitions in strings and is proved in Lothaire, Combinatorics on Words, and in Crochemore, Hancart and Lecroq, Algorithms on Strings, §1.

2. Counting occurrences

Of the pattern in a text. kmp_search already counts them; for just the count, keep a counter instead of a list. With the separator trick, count positions where in P + '#' + T.

Of every prefix of inside itself. For each , how many times does occur in ? The idea, in two steps:

  1. At each position , the longest prefix of ending there has length . So count cnt[π[i]] += 1. This counts each position once, under its longest prefix.
  2. But a position that ends a copy of prefix also ends a copy of every border of that prefix (Lemma 1): prefix , and so on down the chain. So push counts down: for from to 1, cnt[π[k-1]] += cnt[k]. Going from large to small works because , so each count is final before it is pushed further down.
  3. Add 1 to every for the prefix itself (position , which step 1 did not count under , since is a proper border).

Worked on ababcabab, :

Stagecnt[1]cnt[2]cnt[3]cnt[4]cnt[5..9]
after step 1 (count values)22110
push to 23110
push to 33110
( push to cnt[0], which we ignore; push zeros)33110
add 1 (the prefix itself)44221

Check by eye: a occurs at 0, 2, 5, 7 (4 times); ab at 0, 2, 5, 7 (4); aba at 0, 5 (2); abab at 0, 5 (2); longer prefixes once. To count occurrences of each prefix of inside a different text , do step 1 on the values of the text positions of P + '#' + T, then push down using 's , without the "+1". This is Codeforces 432D.

3. The KMP automaton

The search loop has a state, , and reads one character at a time. That is a finite automaton (a machine with states and arrows labelled by characters). The while loop just computes the arrow on the fly. We can compute all arrows in advance:

The third line is the fallback, but done once per (state, character) pair and reused, because means that row is already filled. Total cost , where is the alphabet size. State means "match just completed"; its arrows behave like state 's.

For = abab over the alphabet :

state (matched)on aon bon c
0 ("")100
1 (a)120
2 (ab)300
3 (aba)140
4 (abab, match)300

Read row 3 on a: we had aba, then a arrives, giving text ending abaa. The longest prefix of abab that ends this is a, so state 1. Row 4 on a: text ends ababa, longest prefix ending there is aba, state 3, which is how overlapping matches continue.

flowchart LR
    S0(("0")) -- a --> S1(("1"))
    S1 -- b --> S2(("2"))
    S2 -- a --> S3(("3"))
    S3 -- b --> S4((("4 match")))
    S1 -- a --> S1
    S3 -- a --> S1
    S4 -- a --> S3
    S0 -- "b, c" --> S0
    S1 -- c --> S0
    S2 -- "b, c" --> S0
    S3 -- c --> S0
    S4 -- "b, c" --> S0

Why build it? Three reasons.

  1. Zero delay. Each text character costs exactly one table lookup. No while loop, so it suits hardware and real-time matching (at the cost of memory).
  2. DP over strings that avoid (or contain) a pattern. "How many strings of length over 26 letters do not contain abab?" Let dp[len][q] = number of strings of that length whose automaton state is . Each new letter moves to ; forbid state . That is . With matrix exponentiation on the transition-count matrix it handles (see matrix exponentiation). Combined with digit DP it solves "count strings between A and B avoiding P" (LeetCode 1397). Codeforces 808G maximises occurrences in a string with wildcards the same way.
  3. The bridge to Aho–Corasick. Put many patterns in a trie, give every node a failure link (the longest proper suffix that is a trie node), and fill transitions the same way: that is the Aho–Corasick automaton. KMP is Aho–Corasick with a trie that is a single path.
Deeper: automaton DP, worked for tiny N

Count binary strings of length 3 that do not contain aa (alphabet {a, b}). . Automaton: (forbidden), . Start: dp = [1, 0] (state 0, state 1). After 1 letter: [1, 1]. After 2: state 0 gets dp0 + dp1 (on b) = 2, state 1 gets dp0 (on a) = 1, so [2, 1]. After 3: [3, 2]. Total 5: bbb, bba, bab, abb, aba. It is the Fibonacci numbers, as expected for "no two adjacent a's".

4. Smaller jobs the same table does

  • Longest border ("longest happy prefix"): .
  • Rotation check: B is a rotation of A iff len(A) == len(B) and B occurs in A + A.
  • Shortest palindrome by prepending: the longest palindromic prefix of has length of s + '#' + reverse(s).
  • Merge with overlap: the longest suffix of the current string that is a prefix of the next word is of word + '#' + tail.
  • Number of distinct substrings, incrementally: when appending a character to , the number of new distinct substrings is of reverse(s + c). That is overall: fine for ; use a suffix automaton beyond.
  • String compression by period: the shortest string such that is if , else itself.

Real-world uses

  • Streaming matchers. Any place that must recognise a fixed byte sequence in a stream it cannot rewind: a multipart MIME boundary in an HTTP body parser, a delimiter in a framing protocol, a magic marker in a serial-port or file-carving tool. The state is one integer, which makes KMP the textbook answer for "search in a stream". Many parsers implement exactly this table (sometimes under the name "partial match table").
  • Intrusion detection and antivirus. Multi-pattern scanners such as Snort and ClamAV use Aho–Corasick, the multi-pattern generalisation of the KMP automaton, for signature matching (see Aho–Corasick).
  • Bioinformatics. Motif search in DNA, where the alphabet is tiny (4 letters) and the text is extremely repetitive, which is exactly where naive matching degenerates. The KMP automaton over is also used to compute probabilities of motif occurrence in random sequences (automaton + Markov chain).
  • Periodicity and tandem repeats. Finding the period of a sequence (repeated units in DNA, repeated frames in a signal, the cycle in a sequence of states) uses .
  • What standard libraries actually use. Honesty matters here: strstr, str.find and indexOf usually do not use KMP. glibc's strstr/memmem use the Two-Way algorithm for longer needles (linear worst case, constant space); CPython's str.find uses a Boyer–Moore–Horspool-style "fastsearch" and switched to Two-Way for long needles in Python 3.10; GNU grep uses Boyer–Moore for fixed strings and DFAs for regexes. They pick these because they skip characters on typical text and need no table. KMP remains the right choice when you need guaranteed linear time in a streaming or embedded context, and its prefix function is the right tool for the self-overlap questions above, which none of those algorithms answer.

Pitfalls & edge cases

  • Resetting to 0 after a match. You will miss overlapping occurrences (aa in aaaa gives 2 instead of 3). Use . If the problem wants non-overlapping occurrences, resetting to 0 is correct; read the statement.
  • Using if instead of while for the fallback. One fallback is not always enough. With if, aaab gets instead of : at the b, must fall , but if stops after one fall, compares b with = a, fails, and leaves . The bug passes many small tests (including aabaaab, which needs only one fallback).
  • Off-by-one in the fallback. It is , not . is a length; is indexed by the last position of the prefix.
  • Starting the construction at . must be 0; starting the loop at 0 compares with itself and sets , a non-proper border, and then the fallback loops forever on some inputs. Start at .
  • Separator collisions. In P + '#' + T, # must occur in neither string. For arbitrary bytes or integers, use a value outside the alphabet (−1 in an integer array) or run the two-phase version.
  • Empty pattern or pattern longer than text. Decide the convention for the empty pattern; return nothing when (the code does this naturally).
  • Memory in the separator trick. of P + '#' + T is integers. For a gigabyte text use the two-phase search, which stores only of the pattern.
  • Python string concatenation in a loop for answers like "Compress Words" is quadratic; build a list and join, or keep only the tail you need.
  • Counting prefix occurrences in the wrong order. Pushing counts down must go from long prefixes to short ones; going upwards double-counts or misses chains.
  • Unicode. Matching UTF-16 code units can split a surrogate pair; for user-facing text, normalise (NFC) first, or match code points.

Variations

  • Morris–Pratt vs Knuth–Morris–Pratt (strict borders). The table in this lesson is the Morris–Pratt failure function. Knuth's refinement: if after falling back from to the character equals , the comparison is doomed (the same text character just failed against that same letter), so skip further. The strong table next[j] stores the first border in the chain whose following character differs. Same total; worst-case delay drops from to , where is the golden ratio (Knuth, Morris, Pratt 1977). The prefix function itself is still needed for periods and counting, so most competitive programmers only use the plain version.
  • Z-algorithm. = length of the longest common prefix of and . Convertible to and from in ; see Z-Algorithm, which compares the two.
  • Aho–Corasick. KMP for a dictionary of patterns: trie + failure links + output links. Lesson.
  • KMP on non-strings. Nothing requires characters: run it on integer arrays (find a sequence of differences to match a shape regardless of offset), on lists of tokens, on tree traversals (subtree isomorphism via serialisation), or on 2D grids (Baker–Bird: Aho–Corasick on rows, then KMP on the column of row ids).
  • Matching with "don't care" symbols. KMP breaks, because borders are no longer transitive. Use FFT-based matching or bitset methods (Shift-And / Bitap, the core of agrep).
  • Approximate matching (up to mismatches or edits). Not KMP; see edit-distance DP in string DP, or Bitap.
  • Online pattern: if the pattern grows one character at a time, the prefix function extends in amortised per character. If characters can also be popped, the amortisation breaks; store the automaton row per state (persistent version) to keep per operation.
  • Real-time KMP (Galil 1981) and constant-space linear matching (Galil–Seiferas 1983, Crochemore–Perrin Two-Way 1991) are the theoretical refinements.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Find the Index of the First Occurrence in a String (LeetCode 28) — Return the first index where a needle appears in a haystack. Teaches the basic search.

Hint

Write kmp_search and return the first element, or −1. Then re-solve with pattern + '#' + text and check for .

2. String Matching (CSES 1753) — Count occurrences of a pattern in a string up to characters. Teaches overlaps and why naive fails on big repetitive inputs.

Hint

Count the times reaches ; do not reset to 0. Naive matching times out on inputs like aaaa…a / aaa…a.

3. Longest Happy Prefix (LeetCode 1392) — Longest proper prefix that is also a suffix. Teaches what means.

Solution
def longest_prefix(s):
    return s[:prefix_function(s)[-1]]

level → l, ababab → abab (overlapping border).

4. Repeated Substring Pattern (LeetCode 459) — Is the string several copies of a shorter block? Teaches periods.

Solution
def repeated_substring_pattern(s):
    p = len(s) - prefix_function(s)[-1]   # smallest period
    return p < len(s) and len(s) % p == 0

Why it is enough to test only the smallest period: Fine–Wilf (see Applications). abab → true, aba → false.

5. Rotate String (LeetCode 796) — Is B a rotation of A? Teaches the doubling trick.

Hint

Equal lengths, and B occurs in A + A. KMP makes it .

6. Finding Borders (CSES 1732) — Print the lengths of all borders. Teaches the border chain (Lemma 1).

Hint

Start at and repeat until 0; print the collected lengths in increasing order. abcababcab → 2 5.

7. Finding Periods (CSES 1733) — Print all periods. Teaches the border–period duality.

Hint

Periods are for every border , plus . For abcababcab: 5 8 10. (The CSES statement treats periods as prefixes whose repetition covers the string, which is the same thing.)

8. Repeated String Match (LeetCode 686) — Fewest copies of A so that B is a substring. Teaches bounding the search.

Hint

Repeat A until its length is at least len(B); check with KMP; if not found, try one more copy; otherwise −1. B can start inside the first copy, so more than one extra copy never helps.

9. Shortest Palindrome (LeetCode 214) — Prepend the fewest characters to make a palindrome. Teaches a clever concatenation.

Solution

The answer keeps the longest palindromic prefix of and mirrors the rest in front. A palindromic prefix of is a prefix of that equals a suffix of reverse(s), so it is a border of s + '#' + reverse(s) (the # stops borders from crossing the middle).

def shortest_palindrome(s):
    k = prefix_function(s + "#" + s[::-1])[-1]   # longest palindromic prefix
    return s[k:][::-1] + s

aacecaaa → aaacecaaa; abcd → dcbabcd. , versus for checking every prefix.

10. Password (Codeforces 126B) — Find the longest substring that is a prefix, a suffix, and also occurs somewhere strictly inside. Teaches combining the border chain with "seen in the middle".

Solution

Candidates are the borders of (the chain from ), tried longest first. A border of length also occurs strictly inside iff .

def password(s):
    pi = prefix_function(s)
    inner_max = max(pi[:-1], default=0)
    k = pi[-1]
    while k:
        if k <= inner_max:
            return s[:k]
        k = pi[k - 1]
    return "Just a legend"

fixprefixsuffix → fix; abcdabc → Just a legend. Why the max test works: if for some , then prefix occurs starting at ; its first characters are prefix , which therefore occurs starting at position and ending at , strictly inside. Conversely an inner occurrence of prefix ending at gives .

11. Prefixes and Suffixes (Codeforces 432D) — For every prefix that is also a suffix, say how many times it occurs in the string. Teaches counting occurrences of every prefix.

Solution

Borders from the chain, counts from prefix_occurrences.

def prefixes_and_suffixes(s):
    occ = prefix_occurrences(s)
    pi = prefix_function(s)
    borders, k = [], pi[-1]
    while k:
        borders.append(k)
        k = pi[k - 1]
    return [(b, occ[b - 1]) for b in sorted(borders)] + [(len(s), 1)]

ABACABA → (1, 4), (3, 2), (7, 1). AAA → (1, 3), (2, 2), (3, 1).

12. Compress Words (Codeforces 1200E) — Glue words left to right, each time removing the longest overlap between the end of the result and the start of the next word. Teaches bounding work per step.

Solution

Only the last len(word) characters of the result can overlap, so compute of word + '#' + tail where tail is that suffix; the last value is the overlap. Total work is the total input length.

def compress_words(words):
    res = list(words[0])
    for w in words[1:]:
        tail = "".join(res[-len(w):])
        k = prefix_function(w + "#" + tail)[-1]
        res.extend(w[k:])
    return "".join(res)

I want to order pizza → Iwantorderpizza.

13. Anthem of Berland (Codeforces 808G) — Replace the question marks in a string to maximise the (overlapping) occurrences of a pattern. Teaches DP over the KMP automaton.

Hint

dp[i][q] = best count after characters with automaton state . For a fixed letter, move to ; for ?, try all 26. Add 1 when the new state is . with .

14. Find All Good Strings (LeetCode 1397) — Count strings between two bounds that do not contain an evil substring. Teaches digit DP combined with the automaton.

Hint

State = (position, automaton state, tight-to-lower, tight-to-upper). Transitions use ; a state equal to is dead. , modulo .

Common mistakes & interview follow-ups

"Explain the failure function in one sentence." For each prefix of the pattern, the length of the longest proper prefix that is also a suffix; after a mismatch it tells you how much of the match you can keep.

"Why is KMP linear when there is a while inside a for?" The staircase argument: rises by at most one per character and each fallback lowers it by at least one, so total fallbacks . Name it: amortised analysis, potential function .

"KMP or Rabin–Karp?" KMP: deterministic, no collisions, streaming. Rabin–Karp: simpler to extend to many same-length patterns, 2D matching and substring-equality queries, but probabilistic unless you verify, and attackable with a fixed base. Mention double hashing.

"KMP or Z?" Equivalent power. KMP streams with memory; Z is natural for "for each position, how far does it agree with the start" questions. Many people pick whichever they can write bug-free.

"Why doesn't strstr use KMP?" Boyer–Moore-style and Two-Way algorithms skip characters on typical text and Two-Way needs extra space with the same worst case.

"Find all occurrences of each of patterns." separate KMP runs cost ; Aho–Corasick costs .

"How would you find the smallest period? Is the string a power of a smaller string?" ; power iff and .

"Can you do it in extra space?" Not with KMP (it needs ). Two-Way or Galil–Seiferas do it in constant space and linear time.

Mistakes interviewers watch for: if instead of while for the fallback; instead of ; resetting after a match; starting the prefix-function loop at 0; forgetting the empty-pattern case; claiming "each character is compared at most once" (it is at most twice, amortised).

Quick quiz

1. Compute for aabaaab.

Answer

. The interesting step is : , = a vs = b fails, fall back to , a vs = a matches, so . One fallback was enough here; aaab is the small input where a single if breaks (see Pitfalls).

2. How many times does aa occur in aaaaa, and which line of the code makes the answer correct?

Answer

4 (at 0, 1, 2, 3). The line j = pi[m - 1] after a match, which keeps one a matched. Resetting to 0 would give 2.

3. What is the smallest period of abcabcab, and is the string a repetition of a shorter block?

Answer

, so the period is . Since 3 does not divide 8, it is not a whole repetition (abc abc ab).

4. In the automaton for abab, where does state 4 go on a, and why?

Answer

State 3. After a full match the text ends in abab; adding a makes it end in ababa, whose longest suffix that is a prefix of abab is aba.

5. The text has characters. What is the largest possible total number of fallbacks during one KMP search, whatever the pattern?

Answer

At most (in fact at most ): each fallback decreases by at least 1, increases by at most 1 per character, and always. So the whole search does at most about comparisons.

Further reading / sources

  • Donald E. Knuth, James H. Morris, Vaughan R. Pratt, "Fast pattern matching in strings", SIAM Journal on Computing 6(2), 1977, pp. 323–350. The original paper, including the strict-border refinement and the delay bound.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd/4th ed., chapter "String Matching" (§32.3 finite automata, §32.4 KMP with the potential-function proof).
  • Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithms on Strings, Cambridge University Press, 2007, ch. 1–2 (borders, periods, Fine–Wilf, the MP and KMP tables).
  • Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, ch. 1–3 (the Z-based view of KMP and Boyer–Moore).
  • cp-algorithms: Prefix function. Knuth–Morris–Pratt algorithm (counting prefix occurrences, the automaton, distinct substrings).
  • Zvi Galil, "String matching in real time", Journal of the ACM 28(1), 1981.
  • Maxime Crochemore, Dominique Perrin, "Two-way string-matching", Journal of the ACM 38(3), 1991 (the algorithm behind glibc strstr).
  • N. J. Fine, H. S. Wilf, "Uniqueness theorems for periodic functions", Proceedings of the AMS 16, 1965 (the periodicity lemma).

Previous lesson: String Hashing in Depth · Next lesson: The Z-Algorithm

Related: String Algorithms overview · Aho–Corasick · Strings in Depth · Tries · String DP · Course home