Compute-Prefix (P)

Compute-Prefix (P)

The above Function Computes the prefix function, which determines the shifting of pattern matches within itself.
Step 1 Initialization
set m  length [P]
set Pf [1]  0
set k  0
Step 2 loop, computation of possible shifts
for q  2 to m
while (k> 0 and P[k + 1]  P [q])
set k  Pf [k]
if (P [k + 1] = P [q] ) then
set k  k + 1
set Pf [q] k
Step 3 return value at the point of call
return (Pf)