String matching

The key question is what work repeats: one pattern against text, many prefixes, many dictionary words, or many substring comparisons.

Chooser

flowchart TD
  accTitle: Choosing a string matching structure
  accDescr: KMP or Z handles exact linear matching of one pattern, a Trie handles many dictionary prefixes, rolling hash handles many substring comparisons with collision care, and Aho-Corasick handles many patterns in one text.
  A{"What repeats?"}
  A -->|"one exact pattern"| B["KMP or Z algorithm"]
  A -->|"dictionary prefix queries"| C["Trie"]
  A -->|"substring equality queries"| D["Rolling hash + collision policy"]
  A -->|"many patterns through one text"| E["Aho-Corasick automaton"]

KMP state

longest_border[i] is the length of the longest proper prefix of the pattern that is also a suffix ending at i. On mismatch, it identifies the next viable matched prefix without moving backward in the text.

PythonC++17C++11

def kmp_search(text: str, pattern: str) -> int:
    """Return the first pattern position in text, or ``-1``."""
    if not pattern:
        return 0

    longest_border = [0] * len(pattern)
    border = 0
    for index in range(1, len(pattern)):
        # Reuse the next-shorter border after a mismatch.
        while border and pattern[index] != pattern[border]:
            border = longest_border[border - 1]
        if pattern[index] == pattern[border]:
            border += 1
        longest_border[index] = border

    matched = 0
    for index, character in enumerate(text):
        while matched and character != pattern[matched]:
            matched = longest_border[matched - 1]
        if character == pattern[matched]:
            matched += 1
            if matched == len(pattern):
                # Convert the ending index into the match's start.
                return index - len(pattern) + 1
    return -1

inline int kmp_search(const std::string& text, const std::string& pattern) {
  if (pattern.empty()) {
    return 0;
  }
  std::vector<int> longest_border(pattern.size(), 0);
  int border = 0;
  for (int index = 1; index < static_cast<int>(pattern.size()); ++index) {
    // Reuse the next-shorter border after a mismatch.
    while (border > 0 && pattern[index] != pattern[border]) {
      border = longest_border[border - 1];
    }
    if (pattern[index] == pattern[border]) {
      ++border;
    }
    longest_border[index] = border;
  }

  int matched = 0;
  for (int index = 0; index < static_cast<int>(text.size()); ++index) {
    while (matched > 0 && text[index] != pattern[matched]) {
      matched = longest_border[matched - 1];
    }
    if (text[index] == pattern[matched]) {
      ++matched;
      if (matched == static_cast<int>(pattern.size())) {
        // Convert the ending index into the match's start.
        return index - matched + 1;
      }
    }
  }
  return -1;
}

inline int kmp_search(const std::string& text, const std::string& pattern) {
  if (pattern.empty()) {
    return 0;
  }
  std::vector<int> longest_border(pattern.size(), 0);
  int border = 0;
  for (int index = 1; index < static_cast<int>(pattern.size()); ++index) {
    // Reuse the next-shorter border after a mismatch.
    while (border > 0 && pattern[index] != pattern[border]) {
      border = longest_border[border - 1];
    }
    if (pattern[index] == pattern[border]) {
      ++border;
    }
    longest_border[index] = border;
  }

  int matched = 0;
  for (int index = 0; index < static_cast<int>(text.size()); ++index) {
    while (matched > 0 && text[index] != pattern[matched]) {
      matched = longest_border[matched - 1];
    }
    if (text[index] == pattern[matched]) {
      ++matched;
      if (matched == static_cast<int>(pattern.size())) {
        // Convert the ending index into the match's start.
        return index - matched + 1;
      }
    }
  }
  return -1;
}

Preprocessing and scanning take O(pattern + text) time and O(pattern) space.

Failure checks

• Define the empty-pattern result.
• Distinguish characters from bytes when Unicode rules matter.
• A rolling hash is probabilistic unless collisions are verified or eliminated.
• A Trie is for prefix sharing; it does not find arbitrary substrings by itself.

Practice ladder

1. Find the Index of the First Occurrence in a String — exact matching.
2. Repeated Substring Pattern — border structure.
3. Longest Happy Prefix — final prefix-function value.
4. Shortest Palindrome — match a string against its reverse.