Groups
Category
The Z-function of a string S computes for each position i the length of the longest substring starting at i that matches the prefix of S.
Polynomial string hashing encodes a string as a base-p number modulo a large prime, letting us compare substrings in O(1) after O(n) preprocessing.