DSAverse
String Algorithms
Loading String Algorithms...
Pattern Matching
A
B
A
B
C
A
B
A
B
A
B
A
B
text / pattern
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
String Algorithms
Loading String Algorithms...
Pattern Matching
text / pattern
Go beyond brute-force O(n×m) pattern matching. These linear-time algorithms power search engines, DNA sequencers, and text editors.
Naive matching rescans characters already matched. KMP and Z-Algorithm use precomputed tables to skip ahead safely, achieving O(n+m).
Rabin-Karp slides a hash window across the text. Updating the hash takes O(1) per step, turning O(n×m) into O(n+m) on average.
Both KMP's failure function and the Z-array encode information about how a string's prefixes overlap with its substrings — the key to linear matching.
Step through each algorithm and see exactly why each comparison is skipped
Knuth-Morris-Pratt avoids redundant comparisons by pre-computing a failure function. When a mismatch occurs, the pattern shifts by the maximum safe amount rather than just one position.
O(n + m)O(m)Uses a rolling hash to compare a sliding window of the text with the pattern in O(1) per step. Hash collisions trigger a character-by-character verification.
O(n + m) avgO(1)Computes the Z-array where Z[i] is the length of the longest substring starting at i that matches a prefix of the string. Enables linear-time pattern matching without a separate failure function.
O(n)O(n)The backbone of search, genomics, and natural language processing
Every full-text search — from grep to Ctrl+F — relies on fast pattern matching. KMP and similar algorithms make searching gigabytes of text practical.
DNA and protein sequence alignment requires matching patterns in strings billions of characters long. Linear-time algorithms are not a luxury — they're a necessity.
Rolling-hash algorithms power plagiarism detectors and checksum-based file deduplication. Rabin-Karp is the foundation of the rsync delta-transfer algorithm.