When you're starting out, finding a substring inside a larger string seems straightforward. You might use built-in functions or a simple loop that slides a window across the text. But in competitive programming, where efficiency is everything, these methods are too slow. They often re-check the same characters repeatedly, leading to performance that's quadratic or worse when you have many patterns to find.

To solve complex string problems under tight time limits, you need to move beyond brute-force. Advanced techniques rely on a clever trade-off: spend time preprocessing the text or the patterns once, and then answer queries about them in lightning-fast time. This approach transforms seemingly impossible problems into manageable ones.

Imagine you could convert any string into a single number, its hash. If two strings have the same hash, they are likely identical. This is the idea behind string hashing, a powerful probabilistic tool. The most common method is the Polynomial Rolling Hash an algorithm that assigns a numerical value to a string based on its characters.

The real power of this technique comes from being able to calculate the hash of any substring in constant time, $O(1)$, after a one-time, linear-time preprocessing of the entire string. By pre-calculating the hashes of all prefixes and the necessary powers of $p$, we can find the hash of a substring $S[i..j]$ by subtracting the hash of the prefix ending at $i-1$ from the one ending at $j$.

This makes comparing any two substrings an $O(1)$ operation, a massive improvement over the linear-time comparison required by naive methods. The modular inverse $(p^i)^{-1}$ can be precomputed or found quickly using binary exponentiation, a concept from number theory.

Hashing is great for comparing substrings, but what about finding all occurrences of one or more patterns? For this, we turn to deterministic structures called automata.

KMP's magic lies in its preprocessing of the pattern to create a prefix function, often stored in an array called pi or lps (longest proper prefix which is also a suffix). For each position i in the pattern, pi[i] stores the length of the longest proper prefix of the pattern's prefix P[0...i] that is also a suffix of that same prefix.

When a mismatch occurs while searching, the prefix function tells us exactly how many characters to shift the pattern forward without missing a potential match. This avoids redundant comparisons.

But what if you need to find multiple patterns at once? Running KMP for each pattern would be inefficient. This is where the Aho-Corasick automaton shines. It combines a set of patterns into a single state machine resembling a trie (prefix tree), but with additional "failure links."

After building the trie from all patterns, failure links are added. For each node, its failure link points to the longest proper suffix of the string represented by that node which is also a prefix of some pattern. When traversing the text and a mismatch occurs, you follow the failure link instead of restarting from the root. This allows you to check for all patterns simultaneously in a single pass over the text, achieving a remarkable $O(N + L)$ time complexity, where $L$ is the total length of all patterns.

For even more complex substring problems, we need structures that index every substring of a text. This is where suffix arrays and suffix automata come in.

A Suffix Array is simply an array of integers that stores the starting positions of all suffixes of a string after they have been sorted lexicographically. For a string "banana", the sorted suffixes are "a", "ana", "anana", "banana", "na", "nana". The suffix array would be {5, 3, 1, 0, 2, 4}.

Often paired with a suffix array is the LCP (Longest Common Prefix) array. The LCP[i] entry stores the length of the longest common prefix between the suffixes starting at SuffixArray[i] and SuffixArray[i-1]. This array is crucial for solving problems related to finding the longest repeated substring or the number of unique substrings.

Finally, the Suffix Automaton (or DAWG - Directed Acyclic Word Graph) is the most powerful of these structures. It is the smallest possible automaton that recognizes all substrings of a given string. A key property is that it can be built in $O(N)$ time and space. With a suffix automaton, you can answer a huge variety of queries, like counting the number of occurrences of a pattern or finding the first occurrence, all in time proportional to the pattern's length.

These advanced data structures form a core part of the competitive programmer's toolkit. While they require more effort to learn and implement than basic methods, their performance unlocks solutions to a whole new class of problems. Mastering them is a significant step toward tackling the toughest challenges in string manipulation.