String Algorithms and Pattern Matching
String processing algorithms: KMP, Rabin-Karp, Z-algorithm, suffix trees/arrays, Aho-Corasick, and edit distance (Levenshtein).
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 it when
- You need pattern matching, multi-pattern search or string similarity.
- You are choosing between algorithms for text search.
Watch out for
- 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.
The data
Algorithms
7 rows
| 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 |
Fields
The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.
| Section | Field | Type | Example |
|---|---|---|---|
| algorithms | name | string | Knuth-Morris-Pratt (KMP) |
| algorithms | type | string | Pattern Matching |
| algorithms | time | string | O(n + m) preprocessing + search |
| algorithms | space | string | O(m) |
| algorithms | description | string | Uses failure function (longest proper prefix th… |
| algorithms | use_cases | array | [3 items] |
| algorithms | notes | string | Preprocessing builds π (pi) table; search never… |
| algorithms | build_time | string | O(n) |
Fetch the same bytes
The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.
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 →