String & Greedy Algorithms Mind Map

Every string & greedy algorithms visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.

Recall mode hides the page names. Read the hint, say the name, then click the "?" to check.

1. How the map is organized

Overview of the string & greedy algorithms mind map: Find one pattern, Many patterns, big texts, Encode and compress, Greedy choices, Palindromes, Editing text. — The map at a glance: 6 branches, 20 pages.

Ask what the algorithm does with the text:

Looks for text? One pattern scanned once is find one pattern. Many patterns at once, or an index built over the text, is many patterns, big texts.
Rewrites the text? Making it shorter or safe to send is encode and compress.
Builds an answer by always taking the best-looking next step? That is greedy. Huffman is on two branches: a greedy algorithm that produces a compression code.
Looks for symmetry in the text? Palindromes. Stores text that keeps changing under a cursor? Editing text.

2. The branches side by side

Branch	Preprocessing	Time	Example
Find one pattern	a table or hash of the pattern	KMP O(n + m); Rabin-Karp, Boyer-Moore O(nm) worst	KMP
Many patterns, big texts	trie of patterns, or sorted suffixes	Aho-Corasick O(n + m + matches)	Aho-Corasick
Encode and compress	count symbols, or keep a sliding window	Huffman O(n + k log k)	DEFLATE = LZ77 + Huffman
Greedy choices	sort by the right key	O(n log n)	earliest finish time
Palindromes	# separators between letters	Manacher O(n)	longest palindromic substring
Editing text	split the text into a gap, tree or pieces	gap buffer O(1) at the cursor; rope O(log n)	text editor buffer

3. Five facts to remember

Naive search is O(nm); KMP is O(n + m) because it never moves back in the text.
Rabin-Karp compares hashes first and checks characters only when the hashes match.
Aho-Corasick finds every pattern of a dictionary in one pass over the text.
Huffman codes are prefix-free: no code is the start of another, so decoding needs no separators.
Greedy works only when an exchange argument proves it: earliest finish time is optimal, shortest first is not.

See all string & greedy algorithms pages in the index, or the other mind maps.