Prefix function


Learn more...

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 prefix function 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]`

Knuth-Morris-Pratt algorithm uses prefix function. KMP finds all occurrences of string in another string

You may read more about that function: