Implementation

KMP and a trie in Python, explained, then the same KMP core in C++, Java and TypeScript.

Python: KMP

def prefix_function(p: str) -> list[int]:
    pi = [0] * len(p)                    # pi[i]: longest border of p[:i+1]
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:    # fall back to a shorter border
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi


def kmp_search(text: str, pattern: str) -> list[int]:
    m = len(pattern)
    if m == 0:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    hits, k = [], 0                         # k: matched so far
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == m:
            hits.append(i - m + 1)
            k = pi[k - 1]                   # allow overlaps
    return hits


assert prefix_function("ababaca") == [0, 0, 1, 2, 3, 0, 1]
assert kmp_search("abababcabab", "abab") == [0, 2, 7]
assert kmp_search("aaaa", "aa") == [0, 1, 2]

• while shrinks k on a mismatch, if grows it on a match; both functions share this shape.
• An empty pattern matches everywhere, as with str.find; without the check, pattern[0] fails.
• i - m + 1 turns the match's end i into its start.

Python: a trie with autocomplete

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _walk(self, prefix: str) -> TrieNode | None:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def complete(self, prefix: str, limit: int = 10) -> list[str]:
        start = self._walk(prefix)
        if start is None:
            return []
        out: list[str] = []
        stack = [(start, prefix)]
        while stack and len(out) < limit:
            node, word = stack.pop()
            if node.is_end:
                out.append(word)
            for ch in sorted(node.children, reverse=True):
                stack.append((node.children[ch], word + ch))
        return out


t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
assert t.complete("ca") == ["car", "cart", "cat"]

• A dict of children works for any alphabet; for lowercase only, 26 slots are faster.
• Without is_end, the bare prefix ca would be listed as a word.
• complete uses an explicit stack; children are pushed in reverse so they pop in sorted order.

C++

#include <string>
#include <vector>

std::vector<int> prefixFunction(const std::string& p) {
    std::vector<int> pi(p.size(), 0);
    int k = 0;
    for (size_t i = 1; i < p.size(); ++i) {
        while (k > 0 && p[i] != p[k]) k = pi[k - 1];
        if (p[i] == p[k]) ++k;
        pi[i] = k;
    }
    return pi;
}

std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> hits;
    const int m = static_cast<int>(pattern.size());
    if (m == 0) return hits;
    const std::vector<int> pi = prefixFunction(pattern);
    int k = 0;
    for (size_t i = 0; i < text.size(); ++i) {
        while (k > 0 && text[i] != pattern[k]) k = pi[k - 1];
        if (text[i] == pattern[k]) ++k;
        if (k == m) {
            hits.push_back(static_cast<int>(i) - m + 1);
            k = pi[k - 1];
        }
    }
    return hits;
}

std::string holds bytes, so UTF-8 positions are byte offsets. An empty pattern returns nothing here.

Java

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

public final class Kmp {
    static int[] prefixFunction(String p) {
        int[] pi = new int[p.length()];
        int k = 0;
        for (int i = 1; i < p.length(); i++) {
            while (k > 0 && p.charAt(i) != p.charAt(k)) k = pi[k - 1];
            if (p.charAt(i) == p.charAt(k)) k++;
            pi[i] = k;
        }
        return pi;
    }

    static List<Integer> search(String text, String pattern) {
        List<Integer> hits = new ArrayList<>();
        int m = pattern.length();
        if (m == 0) return hits;
        int[] pi = prefixFunction(pattern);
        int k = 0;
        for (int i = 0; i < text.length(); i++) {
            while (k > 0 && text.charAt(i) != pattern.charAt(k)) k = pi[k - 1];
            if (text.charAt(i) == pattern.charAt(k)) k++;
            if (k == m) {
                hits.add(i - m + 1);
                k = pi[k - 1];
            }
        }
        return hits;
    }
}

charAt returns UTF-16 code units: matching stays exact, but positions count code units.

TypeScript

export function prefixFunction(p: string): number[] {
  const pi = new Array<number>(p.length).fill(0);
  let k = 0;
  for (let i = 1; i < p.length; i++) {
    while (k > 0 && p[i] !== p[k]) k = pi[k - 1];
    if (p[i] === p[k]) k++;
    pi[i] = k;
  }
  return pi;
}

export function kmpSearch(text: string, pattern: string): number[] {
  const hits: number[] = [];
  const m = pattern.length;
  if (m === 0) return hits;
  const pi = prefixFunction(pattern);
  let k = 0;
  for (let i = 0; i < text.length; i++) {
    while (k > 0 && text[i] !== pattern[k]) k = pi[k - 1];
    if (text[i] === pattern[k]) k++;
    if (k === m) {
      hits.push(i - m + 1);
      k = pi[k - 1];
    }
  }
  return hits;
}

Summary

• KMP: shrink k on a mismatch, grow it on a match.
• A trie node holds children and an is_end flag; autocomplete collects words below the prefix node.
• Positions are bytes in C++, UTF-16 units in Java and TypeScript, code points in Python.