api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2907
  slug: string-algorithms
  title: String Algorithms and Pattern Matching
  description: "String processing algorithms: KMP, Rabin-Karp, Z-algorithm, suffix trees/arrays, Aho-Corasick, and edit distance (Levenshtein)."
  summary: "String algorithms and the structures behind them: KMP, Rabin-Karp, the Z-algorithm, suffix trees and arrays, Aho-Corasick and Levenshtein edit distance, each with type, time, space, description, uses and notes."
  use_when[2]: "You need pattern matching, multi-pattern search or string similarity.",You are choosing between algorithms for text search.
  caveats[2]: Complexities assume a fixed alphabet or a stated alphabet size; check the notes.,"For ordinary text search, a library routine is usually the right first choice."
  related[4]: tree-data-structures,dynamic-programming-patterns,bloom-filters-probabilistic,awk-reference
  entry_count: 7
  fields[8]{section,field,type,example}:
    algorithms,name,string,Knuth-Morris-Pratt (KMP)
    algorithms,type,string,Pattern Matching
    algorithms,time,string,O(n + m) preprocessing + search
    algorithms,space,string,O(m)
    algorithms,description,string,Uses failure function (longest proper prefix th…
    algorithms,use_cases,array,"[3 items]"
    algorithms,notes,string,Preprocessing builds π (pi) table; search never…
    algorithms,build_time,string,O(n)
  category: Data Structures
  category_slug: data-structures
  tags: "strings,pattern-matching,kmp,rabin-karp,z-algorithm,suffix-tree,aho-corasick,levenshtein"
  view_count: 40
  created_at: 1778695229
  updated_at: 1778695229
data:
  algorithms[7]:
    - name: Knuth-Morris-Pratt (KMP)
      type: Pattern Matching
      time: O(n + m) preprocessing + search
      space: O(m)
      description: Uses failure function (longest proper prefix that is also suffix) to skip redundant comparisons
      use_cases[3]: Text search in editors,DNA sequence matching,Intrusion detection (signature matching)
      notes: Preprocessing builds π (pi) table; search never backtracks in text
    - name: Rabin-Karp
      type: Pattern Matching (Rolling Hash)
      time: "O(n + m) average, O(nm) worst"
      space: O(1)
      description: Uses hash of pattern and rolling hash of text windows; matches hash before character-by-character verify
      use_cases[4]: Plagiarism detection,Multiple pattern matching,Fingerprinting,Duplicate detection
      notes: Extendable to 2D pattern matching; collision probability managed with double hashing
    - name: Z-Algorithm
      type: Pattern Matching
      time: O(n + m)
      space: O(n + m)
      description: "Computes Z-array: length of longest substring starting at each position that matches a prefix"
      use_cases[3]: String matching,Period detection,Longest common prefix queries
      notes: Concatenate pattern$text with sentinel; Z-values ≥ pattern length indicate matches
    - name: Suffix Tree
      type: String Index
      build_time: O(n)
      space: O(n)
      description: "Compressed trie of all suffixes; enables O(m) pattern search, longest repeated substring, etc."
      use_cases[4]: Genomic sequence analysis,Full-text search,Longest common substring,Palindrome detection
      notes: Ukkonen's algorithm builds in linear time; high constant factor and memory usage in practice
    - name: Suffix Array
      type: String Index
      build_time: O(n log n) or O(n)
      space: O(n)
      description: Sorted array of all suffixes; with LCP array enables most suffix tree operations with less memory
      use_cases[3]: Compressed text indexing,Bioinformatics,Data compression (BWT)
      notes: Binary search for pattern in O(m log n); with LCP array can achieve O(m + log n)
    - name: Aho-Corasick
      type: Multi-pattern Matching
      time: O(n + m + z) where z = number of matches
      space: O(m)
      description: Builds automaton from dictionary of patterns; finds all occurrences of all patterns in one text pass
      use_cases[4]: Virus/malware signature scanning,Keyword highlighting,Content filtering,Aho-Corasick automaton
      notes: Extends KMP failure function to a trie; failure links point to longest proper suffix that is a dictionary prefix
    - name: Levenshtein Distance (Edit Distance)
      type: String Similarity
      time: O(m * n)
      space: "O(min(m,n)) with optimization"
      description: "Minimum number of single-character edits (insert, delete, substitute) to transform one string into another"
      use_cases[5]: Spell checking,Fuzzy search,DNA sequence alignment,Plagiarism detection,OCR error correction
      notes: Dynamic programming; can be optimized with Ukkonen's cutoff for bounded distance queries