Knuth-Morris-Pratt (KMP): Prefix Function π[i] Amortized Linearity & DFA View

1. The Prefix Function $\pi[i]$ & Potential-Function Proof of $\Theta(N)$ Linearity

For a string $S[0..n-1]$, a border of prefix $S[0..i]$ is any proper substring (length $k \le i$) that is simultaneously a prefix and a suffix of $S[0..i]$. The prefix function $\pi[i]$ stores the length of the longest border of $S[0..i]$.

2. Building the Explicit KMP Automaton (DFA) for Worst-Case $O(1)$ Per-Character Streaming

In standard KMP, a single character step can take up to $O(M)$ while-loop hops in the worst case (e.g., on "aaaaab"), even though it is $O(1)$ amortized. What if we are building a real-time network packet scanner, or running Dynamic Programming over strings where we branch into multiple states and cannot rely on amortization? We can precompute the KMP Deterministic Finite Automaton $\text{aut}[j][c]$ in $O(M \cdot |\Sigma|)$ time using a single line:

$$\text{aut}[j][c] = \begin{cases} j + 1 & \text{if } j < M \text{ and } P[j] = c \\ \text{aut}[\pi[j - 1]][c] & \text{if } j > 0 \text{ and } P[j] \neq c \\ 0 & \text{if } j = 0 \text{ and } P[0] \neq c \end{cases}$$

Notice that because $\pi[j - 1] < j$, row $\text{aut}[\pi[j - 1]]$ has already been computed! This eliminates the while loop completely and gives strict worst-case $O(1)$ per character!

3. Production Implementation: Prefix Function, KMP Stream Matcher, Smallest Period & KMP Automaton

/**
 * Computes the KMP Prefix Function pi[0..M-1] in exact Theta(M) time and space.
 * pi[i] = length of longest proper prefix of P[0..i] that is also a suffix of P[0..i].
 */
function computePrefixFunction(pattern) {
  const m = pattern.length;
  const pi = new Int32Array(m);
  let j = 0;
  for (let i = 1; i < m; i++) {
    while (j > 0 && pattern.charCodeAt(i) !== pattern.charCodeAt(j)) {
      j = pi[j - 1];
    }
    if (pattern.charCodeAt(i) === pattern.charCodeAt(j)) {
      j++;
    }
    pi[i] = j;
  }
  return pi;
}

/**
 * Finds all starting indices in text where pattern occurs in Theta(N + M) time and O(M) space.
 */
function kmpSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  if (m === 0) return [];
  const pi = computePrefixFunction(pattern);
  const matches = [];
  let j = 0;

  for (let i = 0; i < n; i++) {
    while (j > 0 && text.charCodeAt(i) !== pattern.charCodeAt(j)) {
      j = pi[j - 1];
    }
    if (text.charCodeAt(i) === pattern.charCodeAt(j)) {
      j++;
    }
    if (j === m) {
      matches.push(i - m + 1);
      j = pi[j - 1]; // Fallback to find overlapping matches!
    }
  }
  return matches;
}

/**
 * Periodicity Theorem: The smallest period length of S is p = N - pi[N - 1].
 * S is a exact repetition of S[0..p-1] iff p divides N.
 */
function smallestExactPeriod(str) {
  const n = str.length;
  const pi = computePrefixFunction(str);
  const p = n - pi[n - 1];
  return n % p === 0 ? str.slice(0, p) : str;
}

/**
 * Builds the explicit KMP DFA Automaton aut[state][charCode] for strict O(1) worst-case transitions
 */
function buildKmpAutomaton(pattern, alphabetSize = 26, baseCharCode = 97) {
  const m = pattern.length;
  const pi = computePrefixFunction(pattern);
  const aut = Array.from({ length: m + 1 }, () => new Int32Array(alphabetSize));

  for (let state = 0; state <= m; state++) {
    for (let c = 0; c < alphabetSize; c++) {
      if (state < m && pattern.charCodeAt(state) - baseCharCode === c) {
        aut[state][c] = state + 1;
      } else if (state > 0) {
        aut[state][c] = aut[pi[state - 1]][c];
      } else {
        aut[state][c] = 0;
      }
    }
  }
  return aut;
}

4. Complexity Matrix