Strings
String problems ask where a word occurs in a text, whether two parts of it are equal, or which part repeats. Comparing character by character is often too slow, and string algorithms answer such questions in about the time it takes to read the text once.
String hashing turns a string into a number, its hash, so that two strings can be compared with one comparison of numbers instead of letter by letter. Prepared once, it gives the hash of every substring of a string in , so substrings can be compared and searched for just as fast. Two different strings can, rarely, get the same hash; to find one pattern in a text with an answer that is always exact, the prefix function or the Z-function is the closer tool.
The prefix function computes, for every position of a string, the length of the longest stretch ending there that repeats the start of the string, in time. With it you can find every occurrence of a pattern in a text read one letter at a time (the KMP algorithm), or the shortest piece a string repeats (its period). The Z-function solves the same problems with a different array.
The Z-function computes, for every position of a string, how many letters from there repeat the start of the string, in time. With it you can find every occurrence of a pattern in a text, or the periods of a string, even when the text has 10^6 letters and the plain letter-by-letter search is too slow.