a suffix automaton
Here is a surprising fact: you can build a tiny machine that recognizes exactly the substrings of a given string. Feed it any sequence of characters, and it ends in an accepting state if and only if that sequence appears somewhere inside your string. A suffix automaton is precisely this machine — the smallest such recognizer — and despite accepting all of the up-to-n^2/2 substrings, it has only a linear number of states and edges.
Formally, the suffix automaton of a string S is the smallest deterministic finite automaton that accepts every suffix of S (and therefore, by following any path, recognizes every substring of S). Its key concept is the 'endpos' set: two substrings are merged into the same state exactly when they occur at the same set of ending positions in S. Grouping substrings this way is what makes the automaton minimal, and a clean theorem guarantees it has at most 2n-1 states and at most 3n-4 transitions for a string of length n — linear, even though it represents quadratically many substrings. It can be built online (adding one character at a time) in O(n) time over a constant alphabet, maintaining 'suffix links' (a parent structure analogous to KMP's failure links) as it grows. Checking whether a pattern P occurs is then just running P through the automaton: O(m) time, success if you never get stuck.
The suffix automaton is a compact powerhouse for substring questions. The number of distinct substrings of S equals a simple sum over states; the number of times a substring occurs equals the size of its endpos set (computable by propagating counts along suffix links); the longest common substring of two strings comes from running one string through the other's automaton. It is closely related to the suffix tree (the suffix automaton of S corresponds to the suffix tree of the reversed S in a precise sense) and often the easiest of the suffix structures to code correctly, with excellent constants. The catch is that its inner workings — endpos equivalence and suffix links — take real effort to understand and prove, so it rewards patience.
For S = "abb", the suffix automaton accepts exactly the substrings a, b, ab, bb, abb (and the empty string). Run "ab": you traverse a then b and land in an accepting state — "ab" is a substring. Run "ba": after 'b' there is no edge for 'a', so you get stuck — "ba" is correctly rejected, as it never appears in "abb".
A minimal automaton recognizing all substrings; running P succeeds iff P occurs in S, in O(|P|).
The linear-size guarantee (at most 2n-1 states) is genuinely surprising given it encodes quadratically many substrings — the endpos equivalence is what compresses it. It is powerful and code-compact but its correctness proof (suffix links, endpos classes) is the subtle part; treat it as advanced.