Tag: strings

Aho-Corasick:Many Patterns, One Pass Over the Text

Build a trie of all needles, add failure links like KMP on a forest, then scan the haystack once — every pattern that ends at the current character reports.

Algorithms

Boyer-Moore:Skip Ahead When the Mismatch Is Near the End

Align the pattern at the window end, use a bad-character skip (and the good-suffix idea) so a late mismatch jumps the haystack instead of sliding by one.

Algorithms

Rabin-Karp:Rolling Hash When You Need Many Pattern Checks

Slide a window hash in O(1), compare hashes first, then verify characters — the procedure for one needle or many needles against the same haystack.

Algorithms

KMP:Find a Pattern Without Sliding Back on the Text

Build the LPS prefix table, then scan the text once — on a mismatch the pattern jumps using already-matched prefix, so the text index never retreats.

Data Structures

Suffix Arrays:Substring Search Without a Full Suffix Tree

A suffix array is the sorted list of a string’s suffixes as start indices. Binary search finds substrings; a short section contrasts the heavier suffix tree.