Pattern Matching
Algorithms that find patterns inside text or sequences.
Pattern matching algorithms locate exact or structured patterns in strings, arrays, and other ordered data.
Naive String Search
Finds a pattern by checking every possible starting position.
Knuth-Morris-Pratt
Finds pattern matches in text by using a prefix table to skip redundant comparisons.
Boyer-Moore
Searches text by comparing from the end of the pattern and making large skips.
Rabin-Karp
Searches for a pattern by comparing rolling hash values.
Aho-Corasick
Finds many patterns in one text scan using an automaton.
Levenshtein Distance
Measures how many insertions, deletions, or substitutions transform one string into another.
Needleman-Wunsch
Globally aligns two sequences with dynamic programming.
Regular Expression Matching
Matches text against patterns with operators such as choice, repetition, and character classes.
Suffix Array Search
Finds substrings by binary searching a sorted array of suffixes.
Z Algorithm
Computes how much each string suffix matches the string prefix.
Dynamic Time Warping
Measures similarity between sequences that may be stretched or shifted in time.
Longest Common Subsequence
Finds the longest sequence that appears in two inputs without requiring contiguous positions.
Hamming Distance
Counts positions where two equal-length strings or vectors differ.
Longest Common Substring
Finds the longest contiguous block shared by two strings.
Smith-Waterman
Finds the best local alignment between two sequences.
Jaro-Winkler Distance
Scores string similarity with extra weight for shared prefixes.
MinHash
Estimates set similarity by comparing compact hash signatures.
Locality-Sensitive Hashing
Hashes similar items into the same buckets with higher probability than dissimilar items.
Suffix Automaton
Represents all substrings of a string in a compact deterministic automaton.
Bitap Algorithm
Searches for patterns by updating bit masks that represent matching prefixes.
Wu-Manber
Searches for multiple patterns using block hashes and shift tables.
Myers Bit-Vector Algorithm
Myers Bit-Vector Algorithm finds exact or approximate matches in text or sequences.
Ukkonen Edit Distance
Ukkonen Edit Distance scores how similar two strings, sets, or sequences are.
BK-Tree Search
BK-Tree Search finds exact or approximate matches in text or sequences.
N-Gram Matching
N-Gram Matching finds exact or approximate matches in text or sequences.
Cosine Similarity
Cosine Similarity scores how similar two strings, sets, or sequences are.
Jaccard Similarity
Jaccard Similarity scores how similar two strings, sets, or sequences are.
Dice Coefficient
Dice Coefficient scores how similar two strings, sets, or sequences are.
Soundex
Soundex finds exact or approximate matches in text or sequences.
Metaphone
Metaphone finds exact or approximate matches in text or sequences.
Damerau-Levenshtein Distance
Damerau-Levenshtein Distance scores how similar two strings, sets, or sequences are.
Optimal String Alignment
Optimal String Alignment aligns sequences with exact or approximate matches.
Sellers Algorithm
Sellers Algorithm finds exact or approximate matches in text or sequences.
BLAST Seed-and-Extend
BLAST Seed-and-Extend aligns sequences with exact or approximate matches.
FM-Index Search
FM-Index Search uses indexed text structure to speed pattern lookup.
Burrows-Wheeler Matching
Burrows-Wheeler Matching finds exact or approximate matches in text or sequences.
Karp-Miller-Rosenberg String Matching
Karp-Miller-Rosenberg String Matching finds exact or approximate matches in text or sequences.
Shortest Common Superstring Greedy
Shortest Common Superstring Greedy handles shortest common superstring by repeatedly merging strings with the largest overlap.
Overlap Graph Superstring
Overlap Graph Superstring addresses shortest common superstring by modeling string overlaps as a weighted graph path problem.
Ukkonen Suffix Tree Construction
Ukkonen Suffix Tree Construction uses maintaining active points and suffix links during online construction for suffix tree construction.
Suffix Automaton LCS
Finds a longest common substring by scanning one string through the suffix automaton of another.
Bit-Parallel Levenshtein
Bit-Parallel Levenshtein addresses edit distance by packing dynamic-programming columns into machine words.
Shift-And Algorithm
Uses bit masks to update all exact-match prefix states in parallel.
Shift-Or Algorithm
Performs exact string matching with bit masks that track unmatched pattern positions.
BNDM
BNDM addresses exact string matching by matching backward with a nondeterministic automaton encoded as bit masks.
Commentz-Walter
Commentz-Walter addresses multiple string matching by combining Boyer-Moore style shifts with trie-based pattern matching.
Galil-Seiferas
Galil-Seiferas addresses exact string matching by using periodicity structure to guarantee linear-time matching with constant space.
Two-Way String Matching
Searches exactly by splitting the pattern at a critical factorization and scanning in two directions.
Crochemore-Perrin
Crochemore-Perrin addresses exact string matching by applying two-way matching with maximal suffix computation.
Manber-Myers Suffix Array Construction
Manber-Myers Suffix Array Construction uses doubling prefix lengths and sorting suffix ranks iteratively for suffix array construction.
SA-IS Suffix Array Construction
SA-IS Suffix Array Construction addresses suffix array construction by inducing suffix order from recursively sorted LMS substrings.
Kasai LCP Algorithm
Computes the LCP array from a suffix array in linear time.
Prefix Function
Computes the longest proper border length for every prefix of a string.
Morris-Pratt
Morris-Pratt uses using prefix borders to avoid rechecking matched characters for exact string matching.
Horspool Algorithm
Finds exact string matches by shifting with the bad-character rule from the pattern's last position.
Sunday Quick Search
Searches for a pattern by shifting according to the character just after the current window.
Gotoh Algorithm
Gotoh Algorithm addresses affine-gap sequence alignment by using separate dynamic-programming states for opening and extending gaps.
Affine Gap Alignment
Affine Gap Alignment addresses sequence alignment by penalizing gap openings more than gap extensions.
Hirschberg Algorithm
Computes sequence alignment using divide and conquer to reduce memory.