String Algorithms and Pattern Matching
String processing algorithms: KMP, Rabin-Karp, Z-algorithm, suffix trees/arrays, Aho-Corasick, and edit distance (Levenshtein).
The data
Algorithms
| Name | Type | Time | Space | Description | Use cases | Notes | Build time |
|---|---|---|---|---|---|---|---|
| Knuth-Morris-Pratt (KMP) | Pattern Matching | O(n + m) preprocessing + search | O(m) | Uses failure function (longest proper prefix that is also suffix) to skip redundant comparisons |
| Preprocessing builds π (pi) table; search never backtracks in text | null |
| Rabin-Karp | Pattern Matching (Rolling Hash) | O(n + m) average, O(nm) worst | O(1) | Uses hash of pattern and rolling hash of text windows; matches hash before character-by-character verify |
| Extendable to 2D pattern matching; collision probability managed with double hashing | null |
| Z-Algorithm | Pattern Matching | O(n + m) | O(n + m) | Computes Z-array: length of longest substring starting at each position that matches a prefix |
| Concatenate pattern$text with sentinel; Z-values ≥ pattern length indicate matches | null |
| Suffix Tree | String Index | null | O(n) | Compressed trie of all suffixes; enables O(m) pattern search, longest repeated substring, etc. |
| Ukkonen's algorithm builds in linear time; high constant factor and memory usage in practice | O(n) |
| Suffix Array | String Index | null | O(n) | Sorted array of all suffixes; with LCP array enables most suffix tree operations with less memory |
| Binary search for pattern in O(m log n); with LCP array can achieve O(m + log n) | O(n log n) or O(n) |
| Aho-Corasick | Multi-pattern Matching | O(n + m + z) where z = number of matches | O(m) | Builds automaton from dictionary of patterns; finds all occurrences of all patterns in one text pass |
| Extends KMP failure function to a trie; failure links point to longest proper suffix that is a dictionary prefix | null |
| Levenshtein Distance (Edit Distance) | String Similarity | O(m * n) | O(min(m,n)) with optimization | Minimum number of single-character edits (insert, delete, substitute) to transform one string into another |
| Dynamic programming; can be optimized with Ukkonen's cutoff for bounded distance queries | null |
Fetch the same bytes
The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.
curl "https://yjtoon.com/api/dataset/string-algorithms?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/string-algorithms.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →