String Algorithms (finding the needle)

Every Ctrl-F, grep, DNA search and spam filter is hunting for one short string inside a much longer one, and the trick that makes that hunt fast is never re-examining a character you already learned something about.

Before you start. You need to be comfortable with an index - a number naming one slot in a list, counting up from the start - and a loop that walks one array one step at a time. The words hash and trie return from Hashing and Trees (BST, balancing, heaps, tries); a one-line reminder rides along the first time each returns.