Suffix tree
Every substring, in linear space.
Weiner's 1973 thesis introduced "position tree" — a tree where every leaf is a suffix and each path is a unique substring. Ukkonen's 1995 algorithm builds it online, in O(n), as the string streams in. The bioinformatics revolution of the 1990s ran on it.
A compressed trie of all suffixes. Internal nodes are labelled with substrings; edges are merged when there's a single-child chain. Every distinct substring of S corresponds to a path from root to some position in the tree.
Computational biology (sequence assembly, mutation finding). Plagiarism detection. Some compression algorithms.
Suffix trees were hot in the 1990s; today suffix arrays + LCP win on memory. But the ideas — particularly Ukkonen's online construction — are foundational and worth understanding.