Prefix Function (KMP)
AlgorithmsMediumCompute the proper prefix-suffix matching table (pi array) and visualize index skips.
Alt+Shift+U
Configuration Panel
Complexity Indices
Time ComplexityO(N)
Auxiliary SpaceO(N) prefix array size
Conceptual Overview
The prefix function (KMP pi array) computes for each prefix of the string the length of its longest proper prefix that is also its suffix. It forms the core of the Knuth-Morris-Pratt pattern matching algorithm.
Source: CP-Algorithms reference guide