Z Function
AlgorithmsMediumCompute longest common prefix matching lengths for all suffixes (Z-array) in linear time.
Alt+Shift+I
Configuration Panel
Complexity Indices
Time ComplexityO(N)
Auxiliary SpaceO(N) Z-array size
Conceptual Overview
The Z-array for string S of length N contains at each index S[i] the length of the longest common prefix of S and S[i..N-1]. Z-Algorithm computes it in O(N) by maintaining active search windows.
Source: CP-Algorithms reference guide