Pattern matching from naive scans to KMP failure functions and rolling hashes.
23 visualizations
Tries the pattern at every text position, comparing character by character — simple but O(nm).
Precomputes a failure function so mismatches skip ahead without ever re-scanning text — O(n + m).
Hashes each text window and only compares characters when hashes collide — average O(n + m).
Computes for every position the longest match with the string's own prefix (Z-array) in O(n), finding all pattern occurrences.
Compares the pattern right-to-left and uses the bad-character rule to skip large chunks of text — often sublinear in practice.
Uses mirrored palindrome radii to find the longest palindromic substring in O(n).
Builds a trie automaton with failure links to find many patterns in one scan.
Sorts suffix indices lexicographically by repeatedly doubling ranked prefixes.
Updates a polynomial window hash in O(1) and verifies equal-hash matches.
Builds the minimal suffix automaton online and uses its transitions to recognize a substring.
Builds one node per distinct palindrome while following palindromic suffix links.
Uses diagonal dynamic-programming lengths to find the longest contiguous match.
Matches the whole text where ? consumes one character and * consumes any sequence.
Eliminates lexicographically larger rotation starts in linear time over the doubled text.
Builds a compressed suffix tree online in linear time.
Reorders text into a compression-friendly last column and reconstructs it exactly.
Constructs the longest-common-prefix array from a suffix array in linear time.
Reconstructs an LCS by divide-and-conquer using linear auxiliary space.
Supports compressed substring search with BWT occurrence ranks.
Constructs suffix ranks by repeatedly doubling compared prefix lengths.
Reports string repetitions by combining internal and crossing runs.
Fills a Unicode edit-distance dynamic-programming matrix.
Builds minimal suffix states, links, and clones.