Prefix function. Knuth-Morris-Pratt algorithm - Preparation to IOI Part 5
Prefix function. Knuth-Morris-Pratt algorithm
Prefix function. Knuth-Morris-Pratt algorithm
Introduction
Strings often overlap with themselves. For example, the string ababa begins with aba and also ends with aba. Such overlaps tell us how much useful progress remains after a mismatch while comparing strings.
The prefix function stores this information for every beginning part of a string. It is the main idea behind the Knuth–Morris–Pratt string-searching algorithm, usually called KMP. With it, we can search for a pattern inside a text without returning to the beginning after every mismatch.
Problem or motivation
Suppose we are given a pattern p and a text t. We want to find every position where p occurs in t.
For example, let p=aba and . The pattern occurs twice:
t=
ababa
it starts at position 1 and covers t[0…2];
it starts at position 3 and covers t[2…4].
The positions in the answer are 1-indexed, although the characters of a C++ string are naturally 0-indexed.
The important difficulty appears after a partial match. If we have already matched many characters and then find a mismatch, starting completely from the beginning may repeat comparisons whose results we already know.
Naive approach
The direct solution tries every possible starting position in the text. At each position, it compares the pattern with the corresponding part of the text character by character.
If the text has length n and the pattern has length m, there are about n possible starts and one attempt may compare m characters. The total time is O(n⋅m). This becomes slow when both strings are long, especially for repetitive strings such as aaaaaaaa....
We can also try to calculate overlap information directly. For every position i, test every possible length k and compare a prefix of length k with the suffix ending at i. A literal implementation of this definition may take O(n3) time, and even a more careful version is still too slow.
Core concept
Prefixes, suffixes, and borders
A prefix of a string begins at its first character. A suffix ends at its last character. A border is a string that is both a prefix and a suffix.
For example, ababa has the following non-empty borders:
a, with length 1;
aba, with length 3.
We only consider proper prefixes, which means that the whole string is not allowed to be its own border. Therefore, the longest border of ababa has length 3, not 5.
Definition of the prefix function
For a string s, the value π[i] is the length of the longest proper prefix of s[0...i] that is also a suffix of s[0...i].
Equivalently, π[i] is the largest length k<i+1 for which
s[0...k−1]=s[i−k+1...i]
If no non-empty border exists, then π[i]=0. Notice that π[i] stores a length, not a character index.
Consider s = "ababaca":
i
s[i]
s[0...i]
Longest border
π[i]
0
a
a
empty
0
1
b
ab
empty
0
2
a
aba
a
1
3
b
abab
ab
2
4
a
ababa
aba
3
5
c
ababac
empty
0
6
a
ababaca
a
1
Thus, the prefix-function array is [0, 0, 1, 2, 3, 0, 1].
How the prefix function is computed
We calculate the values from left to right. Suppose we are currently calculating π[i]. All values before it are already known.
We first look at the previous prefix s[0…i−1]. Its longest border has length π[i−1], so we set
j=π[i−1]
This means that the first j characters of the string already match the last j characters before s[i]. We do not need to compare those characters again. We only need to check whether the new character can extend this match.
The next character after a prefix of length j is s[j]. Therefore, we compare s[i] with s[j].
If they are equal, the old border becomes one character longer, so π[i]=j+1.
If they are different, the border of length j does not work. We try a shorter border.
We do not simply decrease j by one. Most smaller lengths are not borders at all. The next useful candidate is the longest border of s[0…j−1], and its length is already stored in π[j−1]. Therefore, after a mismatch, we jump to
j=π[j−1]
Then we compare s[i] with the new s[j]. If they still differ, we jump again. In this way, we move only through lengths that can actually be borders.
If j becomes 0, there is no smaller non-empty border left. We compare s[i] with the first character s[0]. If they match, then π[i]=1; otherwise, π[i]=0.
For example, consider ababaca when i=5 and the new character is c. The previous prefix ababa has the border aba, so we begin with j=3. To extend it, c would have to match s[3]=b, but it does not. We jump to j=π[2]=1, which means that we now try the shorter border a. It also expects the next character to be b, so it fails as well. We then jump to j=π[0]=0. Since c does not match the first character a, we get π[5]=0.
The trace below shows the complete calculation. Pay special attention to the step at i=5, where j moves from 3 to 1 and then to 0.
Prefix function of ababaca
C++
source · C++line 3
1vector<int> prefix_function(const string &s) {
2 int n = s.size();
3 vector<int> pi(n);
4
5 for (int i = 1; i < n; i++) {
6 int j = pi[i - 1];
7 while (j > 0 && s[i] != s[j]) {
8 j = pi[j - 1];
9 }
10 if (s[i] == s[j]) {
11 j++;
12 }
13 pi[i] = j;
14 }
15 return pi;
16}
Start with pi[0] = 0
L3
A one-character string has no non-empty proper border.
inv
Before processing i, all prefix-function values before i are already correct.
s = "ababaca"7 cells
a
b
a
b
a
c
a
0
1
2
3
4
5
6
i
prefix function7 cells
0
0
0
0
0
0
0
0
1
2
3
4
5
6
pi[0]
i0j-
L3
01 / 15
At first, the while loop may look slow because one position can make several jumps. However, j increases by at most one when we process a new character, and every fallback makes j smaller. Over the whole string, the total number of jumps is O(n), so the complete prefix function is calculated in O(n) time.
Main algorithm
To find pattern p in text t, we build one combined string
s=p+#+t,
where # is a separator that cannot occur in either original string. In our implementation, both input strings contain only lowercase English letters, so # is safe.
Let m be the length of the pattern. At a position belonging to the text, π[i]=m means that the suffix ending at i is equal to the whole pattern. Therefore, an occurrence has just ended. Its 1-indexed starting position in the text is
i−2m+1
Algorithm:
The prefix function of the combined string is calculated in O(n+m) time. We then scan it once, so the complete pattern search also takes O(n+m) time instead of O(n⋅m).
Implementation
Complexity
Prefix function:O(∣s∣) time.
Pattern search:O(∣p∣+∣t∣) time.
Memory:O(∣p∣+∣t∣).
1. Function prefix_function(s)
1.1. Let n be the length of s
1.2. Create an array pi of length n filled with zeroes
1.3. For i from 1 to n - 1
1.3.1. Set j = pi[i - 1]
1.3.2. While j > 0 and s[i] != s[j]
1.3.2.1. Set j = pi[j - 1]
1.3.3. If s[i] == s[j]
1.3.3.1. Set j = j + 1
1.3.4. Set pi[i] = j
1.4. Return pi
2. Function main()
2.1. Configure fast input and output
2.2. Read pattern p and text t
2.3. Let m be the length of p
2.4. Build s = p + "#" + t
2.5. Set pi = prefix_function(s)
2.6. Create an empty array pos
2.7. For i from m + 1 to length(s) - 1
2.7.1. If pi[i] == m, append i - 2 * m + 1 to pos
2.8. Print the size of pos and all positions stored in pos
2.9. Return 0
#include <bits/stdc++.h>using namespace std;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;}int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); string p, t; cin >> p >> t; int m = p.size(); string s = p + "#" + t; vector<int> pi = prefix_function(s); vector<int> pos; for(int i = m + 1; i <(int)s.size(); i++){ if(pi[i] == m){ pos.push_back(i - 2 * m + 1);}} cout << pos.size()<< "\n"; for(int x : pos){ cout << x << " ";} cout << "\n"; return 0;}