api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  id: 58
  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:
    - You need pattern matching, multi-pattern search or string similarity.
    - You are choosing between algorithms for text search.
  caveats:
    - 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:
    - tree-data-structures
    - dynamic-programming-patterns
    - bloom-filters-probabilistic
    - awk-reference
  category: Data Structures
  category_slug: data-structures
  tags: strings,pattern-matching,kmp,rabin-karp,z-algorithm,suffix-tree,aho-corasick,levenshtein
  view_count: 0
  created_at: 1778695229
  updated_at: 1778695229
  entry_count: 7
  fields:
    - section: algorithms
      field: name
      type: string
      example: Knuth-Morris-Pratt (KMP)
    - section: algorithms
      field: type
      type: string
      example: Pattern Matching
    - section: algorithms
      field: time
      type: string
      example: O(n + m) preprocessing + search
    - section: algorithms
      field: space
      type: string
      example: O(m)
    - section: algorithms
      field: description
      type: string
      example: Uses failure function (longest proper prefix th…
    - section: algorithms
      field: use_cases
      type: array
      example: "[3 items]"
    - section: algorithms
      field: notes
      type: string
      example: Preprocessing builds π (pi) table; search never…
    - section: algorithms
      field: build_time
      type: string
      example: O(n)
data:
  algorithms:
    - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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