{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 2497,
        "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"
        ],
        "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\u2026"
            },
            {
                "section": "algorithms",
                "field": "use_cases",
                "type": "array",
                "example": "[3 items]"
            },
            {
                "section": "algorithms",
                "field": "notes",
                "type": "string",
                "example": "Preprocessing builds \u03c0 (pi) table; search never\u2026"
            },
            {
                "section": "algorithms",
                "field": "build_time",
                "type": "string",
                "example": "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": 36,
        "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 \u03c0 (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 \u2265 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"
            }
        ]
    }
}