{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 493,
        "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": 1,
        "created_at": 1781275786,
        "updated_at": 1781275786
    },
    "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"
            }
        ]
    }
}