In the KMP string-search algorithm, what function assigns to each prefix of the pattern the length of its longest proper prefix that is also a suffix?

Prefix function

The prefix function allows the Knuth-Morris-Pratt algorithm to skip redundant comparisons by identifying repeating patterns within the search string itself. By pre-calculating these overlaps, the algorithm achieves a highly efficient linear time complexity of O(n + m). A simple way to remember it is that the function 'remembers' what has already been matched to avoid ever having to move the search pointer backward.