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:
        [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"