Prefix Function

Definition

Prefix Function

The prefix function of a string $P=p_0\dots p_{n-1}$ records the length of the longest proper border of each prefix of $P$:

$$\begin{array}{rl}\pi & :\{0,\dots ,n-1\}\to {\mathbb{N}}_0,\\ \pi (q)& =\max \{k\in \{0,\dots ,q\}:\underset{\text{first }k\text{ characters}}{\underbrace{P[\mathrm{0..}k-1]}}=\underset{\text{last }k\text{ characters of }P[\mathrm{0..}q]}{\underbrace{P[q-k+\mathrm{1..}q]}}\}.\end{array}$$

Stop at index $q$ and consider only $P[\mathrm{0..}q]$. Find the longest string appearing at both ends of this prefix, without taking the whole prefix itself. Its length is $\pi (q)$; characters after $q$ play no part.

The bound $k\le q$ excludes the whole prefix, whose length is $q+1$. For $k=0$, both slices mean the empty string, so $\pi (q)=0$ when no non-empty proper border exists. Otherwise, $\pi (q)$ is the length of the maximal non-trivial border of $P[\mathrm{0..}q]$.

Why the Whole Prefix Is Excluded

Every prefix is a border of itself. Allowing that choice would give $\pi (q)=q+1$ at every position, revealing nothing about repeated characters at its ends. Excluding it makes the function measure how much of the beginning reappears at the current end.

For $q=0$, the inspected prefix contains one character. Its only proper border is $\epsilon$, so $\pi (0)=0$. The empty string is a trivial border, not a non-trivial one.

How Much of a Match Can Be Kept

We want to find $P=\mathrm{ababaca}$. The numbers are zero-based pattern indices.

We search in $T=\mathrm{abababaca}$. These numbers are text indices; they stay fixed when the pattern moves.

Start at text position $0$. The first five characters match, but $T[5]=\mathrm{b}$ disagrees with $P[5]=\mathrm{c}$.

The Naïve Restart

The naïve approach shifts by one and starts again at $P[0]$. Position $1$ fails immediately. At position $2$, it checks aba again before returning to text position $5$.

What the Pattern Alone Tells Us

Set the text aside. The matched prefix $P[\mathrm{0..4}]=\mathrm{ababa}$ has longest proper border aba, so $\pi (4)=3$. Its final three characters are already a copy of the pattern’s first three characters.

A shift of one would require baba to equal abab. It does not. The border therefore identifies the first possible restart: shift by $5-3=2$ and retain three matches. This information depends only on the pattern.

Use the Border to Keep the Match

Bring back the text. Its matched ababa equals the pattern prefix just inspected. Shift directly to position $2$, keep aba without rechecking it, and compare $T[5]$ with $P[3]$.

In general, after $L$ matches and a mismatch:

$$\begin{array}{rl}\text{Retain}& k=\pi (L-1),\\ \text{Shift by}& L-k,\\ \text{Retry}& P[k]\text{ against the same text character}.\end{array}$$

If this comparison also fails, follow the nested borders with $k\leftarrow \pi (k-1)$ for $k>0$. Here $3\to 1\to 0$ gives possible starts $2\to 4\to 5$, skipping starts $1$ and $3$. These are candidates, not guaranteed matches. If even $P[0]$ fails, advance the text position.

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

At $q=4$, the prefix $\mathrm{aba}=P[\mathrm{0..2}]$ equals the suffix $\mathrm{aba}=P[\mathrm{2..4}]$. These occurrences overlap at index $2$, which is allowed.

Appending $\mathrm{c}$ changes the end: no non-empty proper prefix of $\mathrm{ababac}$ ends in $\mathrm{c}$, so the border length falls from $3$ to $0$. Appending the next $\mathrm{a}$ gives a border of length $1$.

$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