# Prefix function

Let's define the prefix function for position i in a string this way:

It's the length of the longest proper prefix of the substring s_(0..i) which is also a suffix of this substring.

We'll denote it as pi.

Mathematically pi_i = max v: v in [0, i], \forall v: s_(0 .. v-1) = s_(i - v + 1 .. i), by definition pi_0=0

For example prefix function from string aa is [0, 1], from aabaaab: [0, 1, 0, 1, 2, 2, 3]

This function is used in Knuth-Morris-Pratt algorithm which helps finding all occurrences of string in another string