a suffix tree
Take a single string and write down every one of its suffixes — for "banana" that is "banana", "anana", "nana", "ana", "na", "a". Now imagine storing all of them in one compressed trie, where shared beginnings share paths and long single-child chains collapse into edges labeled by substrings. That structure is a suffix tree, and it is a remarkably powerful index: once you have built it, an astonishing number of questions about the string become quick walks down the tree.
Concretely, a suffix tree for a string S of length n is a compressed trie containing all n suffixes of S (usually S is given a unique end-marker like '$' so that no suffix is a prefix of another, making every suffix end at its own leaf). Each edge is labeled with a substring of S, each leaf corresponds to one suffix, and every internal node corresponds to a substring that appears at least twice (a repeated, branching context). To check whether a pattern P occurs in S, just walk P down from the root: if you can spell all of P, it occurs, and the leaves below that point tell you exactly where and how many times — so matching takes O(m) time independent of n after the tree is built. The miracle is that the whole tree, despite representing all n suffixes whose total length is about n^2/2, can be built in O(n) time and stored in O(n) space using clever algorithms (Ukkonen's is the famous online one), because the shared structure is compressed away.
A suffix tree turns one preprocessing pass into a Swiss-army knife: longest repeated substring (the deepest internal node), longest common substring of two strings, counting distinct substrings, finding all occurrences of a pattern, and more — many in linear or near-linear time. The honest caveat is the constant factor: a suffix tree carries a lot of pointers and typically uses 10-20+ bytes per character, which for large texts is a real memory burden. That cost is exactly why suffix arrays (a flatter, more cache-friendly alternative) are often preferred in practice, even though the suffix tree is the cleaner object to reason about.
For "banana$", the deepest internal node spells "ana", which has two leaves below it — telling you "ana" is the longest substring that repeats (it occurs at positions 1 and 3). To test if "nan" occurs, walk n-a-n from the root; you can, and the single leaf below pinpoints its one occurrence at position 2.
Every suffix is a root-to-leaf path; the deepest branching node gives the longest repeated substring.
Linear-time construction (Ukkonen, McCreight) is real but intricate, and the structure is memory-heavy (often 10-20 bytes per character). For many tasks a suffix array plus an LCP array gives the same power with a smaller, simpler, more cache-friendly footprint.