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)."
  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
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"