Prefix function. Knuth-Morris-Pratt algorithm - Course 5

Module 1: String Algorithms

String Hashing Algorithms
Z-function
Prefix function. Knuth-Morris-Pratt algorithm
Manacher's Algorithm

Module 2: Graph Algorithms

Kuhn's algorithm — maximum matching in a bipartite graph
Kőnig's theorem

Module 3: Various DP ideas

DP on a DAG
DP subtree
Connected Component DP
Open and Close Interval Trick
DP on Subarrays
Submask DP
Digit DP

Module 4: Combinatorics

Inclusion-Exclusion (Advanced)

Module 5: Meet-in-the-middle

Meet in the Middle

Module 6: Fenwick Tree

Fenwick Tree

Module 7: Centroid Decomposition

Centroid Decomposition

Module 8: Virtual Trees

Virtual Tree / Auxiliary Tree

Module 9: Parallel Binary Search

Parallel binary search

Module 10: [BONUS]

Bitset Optimization
Hashing techniques

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 5/Module 1: String Algorithms/Prefix function. Knuth-Morris-Pratt algorithm

Prefix function. Knuth-Morris-Pratt algorithm

Prefix function. Knuth-Morris-Pratt algorithm

Definition

Given a string $S$ of length $N$ .

The prefix function $\pi(i)$ of the string $S$ for position $i$ $(0 \le i < N)$ is the length of the longest proper prefix of the substring that is also its suffix.

Up next

Manacher's Algorithm

Manacher's Algorithm

i

<

N)

S[0 \dots i]

(A proper prefix is not equal to the whole string.)

Formally:

\pi_i = \max \{ k \mid 0 \le k \le i,\; S[0 \dots k-1] = S[i-k+1 \dots i] \}

By convention:

\pi_0 = 0

Example:

S = \text{"aabcaa"} \Rightarrow \pi = [0,1,0,0,1,2]

Algorithm

Observation 1

For any $0 < i < N$ :

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

Observation 2

If:

S_i = S_{\pi_{i-1}}

then:

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

Otherwise, you need to look for a shorter prefix.

Let:

j = \pi_{i-1}

Then move to:

j = \pi_{j-1}

and check again, until:

$j = 0$ , or
a match is found

If a match is found:

S_i = S_j \Rightarrow \pi_i = j + 1

Otherwise:

\pi_i = 0

Observation 3

The maximum proper prefix of the string $S[0 \dots i]$ that is its suffix equals $\pi_{i-1}$ (if $i>0$ ).

Efficient algorithm

For $i = 1 \dots N-1$ :

$j = \pi_{i-1}$
While $j > 0$ and $S_i \ne S_j$ : $j = \pi_{j-1}$
If $S_i = S_j$ , increment $j$
$\pi_i = j$

Asymptotics:

O(N)

Implementation

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

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

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

        pi[i] = j;
    }

    return pi;
}