Prefix Function Knuth–Morris–Pratt Algorithm

Definition

Given a string $S$ of length $N$ , the prefix function $\pi(i)$ at position $i$ $(0 \leq i < N)$ is the length of the longest proper prefix of the substring

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

CODEFORCESPassword

Rating: 1700

CODEFORCESPrefix Function Queries

Rating: 2200

CODEFORCESAnthem of Berland

Rating: 2300

S[0 \ldots i]

that is also a suffix of this substring.

Here, a proper prefix means a prefix that is not equal to the entire string itself.

So we always have:

\pi_0 = 0

and for $0 < i < N$ :

\pi_i = \max \left\{ k : 0 \le k \le i,\; S[0 \ldots k-1] = S[i-k+1 \ldots i] \right\}

For example, for the string

S = \text{"aabcaa"}

the prefix function is

\pi = [0, 1, 0, 0, 1, 2]

Algorithm

To compute the prefix function efficiently, we use several important observations.

First Observation

For every $0 < i < N$ , we have:

\pi_i \le \pi_{i-1} + 1

This means that the prefix value can increase by at most one when we move to the next position.

Second Observation

Suppose we already know $\pi_{i-1}$ .

Let

j = \pi_{i-1}

Then we try to extend the current match by comparing:

S[i]
S[j]

If they are equal, then we can increase the prefix length by one:

\pi_i = j + 1

Otherwise, we cannot extend the current prefix, so we need to try a shorter one.

The next candidate is:

j = \pi_{j-1}

We repeat this process until:

we find a match, or
$j$ becomes zero.

If no match is found, then:

\pi_i = 0

Implementation

vector<int> prefix_function(string s) {
    vector<int> p(s.size());

    for (int i = 1; i < (int)s.size(); i++) {
        int j = p[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = p[j - 1];
        }

        if (s[i] == s[j]) {
            j += 1;
        }

        p[i] = j;
    }

    return p;
}