Prefix Function

computation

Definition

Prefix Function

Given a string $P$ of length $n$, the prefix function $\pi :\{0,\dots ,n-1\}\to \mathbb{N}$ maps each index $q$ to the length of the longest prefix of $P$ that is a suffix of $P[\mathrm{0..}q]$ and strictly shorter than $P[\mathrm{0..}q]$.

$$\pi (q)=\max \{k\le q\mid P[\mathrm{0..}k-1]=P[q-k+\mathrm{1..}q]\}$$

Equivalently, $\pi (q)$ is the length of the maximal non-trivial border of the prefix $P[\mathrm{0..}q]$. For $q=0$, we have $\pi (0)=0$ (the only non-trivial border of a single character is $\epsilon$).

Examples

$P=\text{ababaca}$

$q$	$P[\mathrm{0..}q]$	$\pi (q)$
0	a	0
1	ab	0
2	aba	1
3	abab	2
4	ababa	3
5	ababac	0
6	ababaca	1

For $q=4$, the prefix $\text{aba}=P[\mathrm{0..2}]$ equals the suffix $\text{aba}=P[\mathrm{2..4}]$; they may overlap.

$P=\text{aaaa}$

$q$	$P[\mathrm{0..}q]$	$\pi (q)$
0	a	0
1	aa	1
2	aaa	2
3	aaaa	3

$P=\text{abcab}$

$q$	$P[\mathrm{0..}q]$	$\pi (q)$
0	a	0
1	ab	0
2	abc	0
3	abca	1
4	abcab	2