Z-Algorithm

For every position in a string, the Z-Algorithm computes the length of the longest substring starting at that position that matches a prefix of the string. The result, called the Z-array, solves pattern matching, string-period detection, and several related problems in linear time.