Z Algorithm

The Z algorithm computes, for every position in a string, the length of the longest substring starting at that position that matches a prefix of the string itself, storing these lengths in an array called the Z array, and does so for the entire string in linear time by reusing previously computed matches to avoid recomparing characters a prior match has already confirmed. Concatenating a pattern, a separator character not present in either string, and a text together and running the Z algorithm on the result gives an efficient single-pattern string matching method, since a Z value equal to the pattern's length marks an occurrence of the pattern in the text. The technique is a standard building block in competitive programming and string processing.