Find every occurrence of he, she, his, hers in "ushers" in one pass. Start from the trie of the patterns. Each node stands for the string on the path to it. Its failure link points to the deepest other node whose string is a suffix of that one, which is where the scan continues when the next letter fits nothing below. Failure links are computed in BFS order, because a node's link depends only on shallower nodes.
Aho-Corasick over 4 patterns.
Depth 1: a single letter has no shorter suffix but the empty string, so every depth-1 node fails to the root. The orange edges marked f are failure links.
Depth-one nodes fail to the root.
Node "he": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a e child there.
Failure link of he set.
Node "hi": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a i child there.
Failure link of hi set.
Node "sh": drop its first letter and the longest suffix that is also in the trie is "h", so that is its failure link. Found by following the parent's failure link to the root and looking for a h child there.
Failure link of sh set.
Node "her": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a r child there.
Failure link of her set.
Node "his": drop its first letter and the longest suffix that is also in the trie is "s", so that is its failure link. Found by following the parent's failure link to the root and looking for a s child there.
Failure link of his set.
Node "she": drop its first letter and the longest suffix that is also in the trie is "he", so that is its failure link. Found by following the parent's failure link to "h" and looking for a e child there. Patterns ending here: she, he. The shorter one ends at the failure node.
Failure link of she set.
Node "hers": drop its first letter and the longest suffix that is also in the trie is "s", so that is its failure link. Found by following the parent's failure link to the root and looking for a s child there.
Failure link of hers set.
Read 'u' at position 0. Nothing continues, back at the root.
Read u. State root.
Read 's' at position 1. Now at "s".
Read s. State s.
Read 'h' at position 2. Now at "sh".
Read h. State sh.
Read 'e' at position 3. Now at "she". "she", "he" end here: match at position 1.
Read e. State she.
Read 'r' at position 4. No r child from the current node: follow 1 failure link first. Now at "her".
Read r. State her.
Read 's' at position 5. Now at "hers". "hers" ends here: match at position 2.
Read s. State hers.
3 matches: she at 1, he at 2, hers at 2. The scan read each of the 6 letters once and never went back, because a failure link already knows the longest pattern prefix that survives a mismatch. Building the links is O(total pattern length), the scan is O(text + matches), and the number of patterns does not appear: that is why it is the algorithm behind grep -F with many words and intrusion detection systems.
3 matches found.