The Prefix Function and the KMP Algorithm

Definitions of String Prefixes and Suffixes

For definitions of prefixes, proper prefixes, suffixes, and proper suffixes of strings, see String Basics.

Prefix Function

Definition

Given a string of length $n$, denoted $s$, its prefix function is defined as an array of length $n$ denoted $\pi$. The definition of $\pi[i]$ is:

1. If the substring $s[0\dots i]$ has a pair of equal proper prefix and proper suffix, namely $s[0\dots k-1]$ and $s[i - (k - 1) \dots i]$, then $\pi[i]$ is the length of this equal proper prefix (or proper suffix, since they are equal), that is, $\pi[i]=k$;
2. If there is more than one such pair, $\pi[i]$ is the length of the longest pair;
3. If no equal pair exists, $\pi[i]=0$.

In simple terms, $\pi[i]$ is the length of the longest equal proper prefix and proper suffix of the substring $s[0\dots i]$.

In mathematical notation:

In particular, define $\pi[0]=0$.

Process

For example, consider the string abcabcd.

$\pi[0]=0$, because a has no proper prefix or proper suffix, so it is 0 by definition.

$\pi[1]=0$, because ab has no equal proper prefix and proper suffix.

$\pi[2]=0$, because abc has no equal proper prefix and proper suffix.

$\pi[3]=1$, because abca has exactly one pair of equal proper prefix and proper suffix: a, of length 1.

$\pi[4]=2$, because the only equal proper prefix and proper suffix of abcab is ab, of length 2.

$\pi[5]=3$, because the only equal proper prefix and proper suffix of abcabc is abc, of length 3.

$\pi[6]=0$, because abcabcd has no equal proper prefix and proper suffix.

Similarly, the prefix function of aabaaab is $[0, 1, 0, 1, 2, 2, 3]$.

Naive Algorithm for Computing the Prefix Function

Process

An algorithm that computes the prefix function directly from its definition proceeds as follows:

• In a loop, for $i = 1\to n - 1$, compute the prefix-function values $\pi[i]$ in order, with $\pi[0]$ assigned $0$.
• To compute the current prefix-function value $\pi[i]$, try the variable $j$ from the largest possible proper-prefix length $i$ downward.
• If the proper prefix and proper suffix of the current length are equal, then this length is $\pi[i]$; otherwise, decrease j by 1 and continue matching until $j=0$.
• If $j = 0$ and no match has been found, set $\pi[i] = 0$ and move to the next index $i + 1$.

// Note:
// string substr (size_t pos = 0, size_t len = npos) const;
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = i; j >= 0; j--)
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(i, -1, -1):
            if s[0:j] == s[i - j + 1 : i + 1]:
                pi[i] = j
                break
    return pi

static int[] prefix_function(String s) {
    int n = s.length();
    int[] pi = new int[n];
    for (int i = 1; i < n; i++) {
        for (int j = i; j >= 0; j--) {
            if (s.substring(0, j).equals(s.substring(i - j + 1, i + 1))) {
                pi[i] = j;
                break;
            }
        }
    }
    return pi;
}

The time complexity of this algorithm is $O(n^3)$, leaving considerable room for improvement.

Efficient Algorithms for Computing the Prefix Function

First Optimization

The first important observation is that adjacent prefix-function values increase by at most $1$.

As shown below, when taking the largest possible $\pi[i+1]$, the newly added character $s[i+1]$ must match the corresponding character, namely $s[i+1]=s[\pi[i]]$; in this case, $\pi[i+1] = \pi[i]+1$.

Therefore, when moving to the next position, the prefix-function value either increases by one, remains unchanged, or decreases.

vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = pi[i - 1] + 1; j >= 0; j--)  // improved: j=i => j=pi[i-1]+1
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        for j in range(pi[i - 1] + 1, -1, -1):
            if s[0:j] == s[i - j + 1 : i + 1]:
                pi[i] = j
                break
    return pi

static int[] prefix_function(String s) {
    int n = s.length();
    int[] pi = new int[n];
    for (int i = 1; i < n; i++) {
        for (int j = pi[i - 1] + 1; j >= 0; j--) {
            if (s.substring(0, j).equals(s.substring(i - j + 1, i + 1))) {
                pi[i] = j;
                break;
            }
        }
    }
    return pi;
}

In this first improved algorithm, when computing each $\pi[i]$, the best case is that the first string comparison produces a match, so the baseline number of string comparisons is $n-1$.

Because j = pi[i-1]+1 (pi[0]=0) limits the maximum number of string comparisons, we can see that only the best case adds $1$ to the upper bound on the number of comparisons; every comparison beyond the first consumes room for growth in later iterations.

Thus the case with the maximum number of comparisons has at least $1$ comparison consumed and at most $n-2$ comparisons accumulated, giving $n-1 + n-2 = 2n-3$ comparisons.

Therefore, after this optimization, computing the prefix function requires only $O(n)$ string comparisons, and the total complexity decreases to $O(n^2)$.

Second Optimization

The first optimization considered the best case when computing $\pi[i+1]$: $s[i+1]=s[\pi[i]]$, giving $\pi[i+1] = \pi[i]+1$. Let us go further and consider how to jump when $s[i+1] \neq s[\pi[i]]$.

As shown above, when a mismatch occurs, we want to find, for the substring $s[0\dots i]$, the second-largest length after $\pi[i]$, namely $j$, while preserving the prefix property at position $i$, namely $s[0 \dots j - 1] = s[i - j + 1 \dots i]$:

If such a length $j$ is found, only $s[i + 1]$ and $s[j]$ need to be compared again. If they are equal, then $\pi[i + 1] = j + 1$. Otherwise, for the substring $s[0\dots i]$, find the second-largest length after $j$, namely $j^{(2)}$, while preserving the prefix property, and repeat until $j = 0$. If $s[i + 1] \neq s[0]$, then $\pi[i + 1] = 0$. The second comparison is illustrated below.

From the figure, because $s[0\dots \pi[i]-1] = s[i-\pi[i]+1\dots i]$, for $s[0\dots i]$ the second-largest length is $j$, with the property

The diagram for this formula is shown below:

In other words, $j$ is equivalent to the prefix-function value of the substring $s[\pi[i]-1]$, corresponding to the lower half of the figure above, namely $j=\pi[\pi[i]-1]$. Similarly, the second-largest length after $j$ is equivalent to the prefix-function value of $s[j-1]$, $j^{(2)}=\pi[j-1]$.

Clearly, we obtain the following state transition for $j$: $j^{(n)}=\pi[j^{(n-1)}-1], \ \ (j^{(n-1)}>0)$.

Final Algorithm

Thus we can construct an algorithm that performs no string comparisons and only $O(n)$ operations.

Moreover, its implementation is surprisingly short and intuitive:

vector<int> prefix_function(string s) {
  int n = (int)s.length();
  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;
}

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

static int[] prefix_function(String s) {
    int n = s.length();
    int[] pi = new int[n];
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s.charAt(i) != s.charAt(j)) {
            j = pi[j - 1];
        }
        if (s.charAt(i) == s.charAt(j)) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

This is an online algorithm: it processes data as it arrives. For example, the string can be read one character at a time and the prefix-function value of each character can be computed immediately. The algorithm still needs to store the string itself and the previously computed prefix-function values, but if the maximum possible prefix-function value of the string is known in advance to be $M$, then it is enough to store the first $M + 1$ characters and their corresponding prefix-function values.

Applications

Finding a Substring in a String: The Knuth–Morris–Pratt Algorithm

This algorithm was jointly published by Knuth, Pratt, and Morris in 1977¹. This task is a typical application of the prefix function.

Process

Given a text $t$ and a string $s$, find and report all occurrences of $s$ in $t$.

For convenience, let $n$ denote the length of $s$, and $m$ the length of the text $t$.

Construct the string $s + \# + t$, where $\#$ is a delimiter that appears in neither $s$ nor $t$, and compute its prefix function. Now consider the meaning of the remaining prefix-function values after the first $n + 1$ values, which belong to $s$ and the delimiter. By definition, $\pi[i]$ is the length of the longest proper substring whose right endpoint is $i$ and which is also a prefix; in this setting, it is the length of the longest substring matching a prefix of $s$ and ending at $i$. Because the delimiter exists, this length cannot exceed $n$. If $\pi[i] = n$, then $s$ occurs in full at this position, that is, its right endpoint is at position $i$. Note that this index is with respect to the string $s + \# + t$.

Therefore, at a position $i$, if $\pi[i] = n$, then the string $s$ occurs in $t$ at position $i - (n - 1) - (n + 1) = i - 2n$. The diagram below illustrates the indices.

As mentioned when computing the prefix function, if we know that the prefix-function value never exceeds a fixed value, we do not need to store the entire string and prefix function; only their initial parts are needed. In this case, we only need to store $s + \#$ and the corresponding prefix-function values. We can read one character of $t$ at a time and compute the prefix-function value at the current position.

Thus the Knuth–Morris–Pratt algorithm (KMP) solves the problem in $O(n + m)$ time and $O(n)$ memory.

vector<int> find_occurrences(string text, string pattern) {
  string cur = pattern + '#' + text;
  int sz1 = text.size(), sz2 = pattern.size();
  vector<int> v;
  vector<int> lps = prefix_function(cur);
  for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
    if (lps[i] == sz2) v.push_back(i - 2 * sz2);
  }
  return v;
}

def find_occurrences(t, s):
    cur = s + "#" + t
    sz1, sz2 = len(t), len(s)
    ret = []
    lps = prefix_function(cur)
    for i in range(sz2 + 1, sz1 + sz2 + 1):
        if lps[i] == sz2:
            ret.append(i - 2 * sz2)
    return ret

static List<Integer> find_occurrences(String text, String pattern) {
    String cur = pattern + '#' + text;
    int sz1 = text.length(), sz2 = pattern.length();
    List<Integer> v = new ArrayList<>();
    int[] lps = prefix_function(cur);
    for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
        if (lps[i] == sz2) {
            v.add(i - 2 * sz2);
        }
    }
    return v;
}

Periods of a String

For a string $s$ and $0 < p \le |s|$, if $s[i] = s[i+p]$ holds for every $i \in [0, |s| - p - 1]$, then $p$ is called a period of $s$.

For a string $s$ and $0 \le r < |s|$, if the prefix of $s$ of length $r$ equals the suffix of length $r$, then the prefix of $s$ of length $r$ is called a border of $s$.

The existence in $s$ of a border of length $r$ implies that $|s|-r$ is a period of $s$.

By the definition of the prefix function, all border lengths of $s$ are $\pi[n-1],\pi[\pi[n-1]-1], \ldots$.²

Therefore, in $O(n)$ time, all periods of $s$ can be found. Since $\pi[n-1]$ is the length of the longest border of $s$, $n - \pi[n-1]$ is the shortest period of $s$.

Counting the Occurrences of Each Prefix

We discuss two problems. Given a string of length $n$, denoted $s$, the first variant asks for the number of occurrences of each prefix $s[0 \dots i]$ in the same string, while the second asks for the number of occurrences of each prefix $s[0 \dots i]$ in another given string $t$.

First consider the first problem. At position $i$, consider the prefix-function value $\pi[i]$. By definition, it means that a prefix of $s$ of length $\pi[i]$ occurs at position $i$ and ends at $i$, and that no longer prefix satisfies this definition. At the same time, shorter prefixes may also end at this position. We encounter a question already answered when computing the prefix function: given a prefix of length $j$ that is also a suffix ending at $i$, what is the next smaller prefix length $k < j$ that is also a suffix ending at $i$? Therefore, with right endpoint $i$, there is a prefix of length $\pi[i]$, a prefix of length $\pi[\pi[i] - 1]$, a prefix of length $\pi[\pi[\pi[i] - 1] - 1]$, and so on, until the length becomes $0$. Thus we can compute the answer as follows.

vector<int> ans(n + 1);
for (int i = 0; i < n; i++) ans[pi[i]]++;
for (int i = n - 1; i > 0; i--) ans[pi[i - 1]] += ans[i];
for (int i = 0; i <= n; i++) ans[i]++;

ans = [0] * (n + 1)
for i in range(0, n):
    ans[pi[i]] += 1
for i in range(n - 1, 0, -1):
    ans[pi[i - 1]] += ans[i]
for i in range(0, n + 1):
    ans[i] += 1

Explanation

In the code above, first count how many times each prefix-function value appears in the array $\pi$, then compute the final answer: if a prefix of length $i$ occurs exactly $\text{ans}[i]$ times, this value must be added to the occurrence count of its longest substring that is both a suffix and a prefix. Finally, to count the original prefix, add $1$ to each result.

Now consider the second problem. Apply the technique from Knuth–Morris–Pratt: construct $s + \# + t$ and compute its prefix function. The only difference from the first problem is that we care only about prefix-function values related to $t$, namely those with $i \ge n + 1$, namely $\pi[i]$. Once these values are known, apply the same algorithm as in the first problem.

Number of Distinct Substrings in a String

Given a string of length $n$, denoted $s$, we want to compute the number of distinct substrings.

We solve this problem iteratively. In other words, given the current number of distinct substrings, we need a way to recompute it after appending one character to the end of $s$.

Let $k$ be the current number of distinct substrings of $s$. Append a new character $c$ to $s$. Clearly, some new substrings ending in $c$ will appear. We want to count those ending in this character that have not appeared before.

Construct $t = s + c$ and reverse it to obtain $t^{\sim}$. The task is now to determine how many prefixes of $t^{\sim}$ do not occur anywhere else in $t^{\sim}$. If the maximum prefix-function value of $t^{\sim}$ is $\pi_{\max}$, then the longest prefix that occurs in $s$ has length $\pi_{\max}$. Naturally, every shorter prefix also occurs.

Therefore, the number of new substrings after adding a new character is $|s| + 1 - \pi_{\max}$.

Thus, for each appended character, the number of new substrings can be computed in $O(n)$ time, giving total complexity $O(n^2)$.

It is worth noting that we can also recompute the number of distinct substrings when adding a character at the beginning, or removing a character from the end or beginning.

String Compression

Given a string of length $n$, denoted $s$, find its shortest “compressed” representation: the shortest string $t$ such that $s$ can be represented by concatenating one or more copies of $t$.

Clearly, we only need to find the length of $t$. Once the length is known, the answer is the prefix of $s$ of that length.

Compute the prefix function of $s$. Using its final value $\pi[n - 1]$, define $k = n - \pi[n - 1]$. We will prove that if $k$ divides $n$, then $k$ is the answer; otherwise no valid compression exists, and the answer is $n$.

Assume that $n$ is divisible by $k$. Then the string can be divided into blocks of length $k$. By the definition of the prefix function, its prefix of length $n - k$ equals its suffix. This means that the last block equals the second-to-last block, the second-to-last equals the third-to-last, and so on. Consequently, all blocks are equal, so $s$ can be compressed to length $k$.

Constructing an Automaton from the Prefix Function

Let us return to the new string formed by concatenating two strings with a delimiter. For strings $s$ and $t$, compute the prefix function of $s + \# + t$. Clearly, because $\#$ is a delimiter, the prefix-function value never exceeds $|s|$. Therefore, we only need to store $s + \#$ and its corresponding prefix-function values, after which we can compute the prefix-function values for all subsequent characters dynamically:

In fact, knowing the next character of string $t$, namely $c$, and the prefix-function value at the previous position is enough to compute the next prefix-function value; no other character or prefix-function value of $t$ is needed.

In other words, we can construct an automaton (a finite-state machine): its state is the current prefix-function value, and the transition from one state to another is determined by the next character.

Thus, even without the string $t$, we can construct a transition table $( \text { old } \pi , c ) \rightarrow \text { new } _ { - } \pi$ using the construction algorithm:

void compute_automaton(string s, vector<vector<int>>& aut) {
  s += '#';
  int n = s.size();
  vector<int> pi = prefix_function(s);
  aut.assign(n, vector<int>(26));
  for (int i = 0; i < n; i++) {
    for (int c = 0; c < 26; c++) {
      int j = i;
      while (j > 0 && 'a' + c != s[j]) j = pi[j - 1];
      if ('a' + c == s[j]) j++;
      aut[i][c] = j;
    }
  }
}

In this form, for a lowercase alphabet, the time complexity is $O(|\Sigma|n^2)$. We can apply dynamic programming to reuse the parts already computed in the table. Whenever we move from $j$ to $\pi[j - 1]$, we are saying that the state reached by transition $(j, c)$ is the same as that reached by transition $(\pi[j - 1], c)$, and the latter answer has already been computed exactly.

void compute_automaton(string s, vector<vector<int>>& aut) {
  s += '#';
  int n = s.size();
  vector<int> pi = prefix_function(s);
  aut.assign(n, vector<int>(26));
  for (int i = 0; i < n; i++) {
    for (int c = 0; c < 26; c++) {
      if (i > 0 && 'a' + c != s[i])
        aut[i][c] = aut[pi[i - 1]][c];
      else
        aut[i][c] = i + ('a' + c == s[i]);
    }
  }
}

The automaton can ultimately be constructed in $O(|\Sigma|n)$ time.

When is this automaton useful? First, recall that most of the time we use the prefix function of $s + \# + t$ for one purpose: finding all occurrences of $s$ in $t$.

Therefore, the most direct benefit of this automaton is accelerating the computation of the prefix function of $s + \# + t$.

By constructing the automaton for $s + \#$, we no longer need to store $s$ or its corresponding prefix-function values. All transitions have already been computed in the table.

There is also a second, less direct application. When $t$ is a huge string constructed by rules, the automaton can accelerate the computation. Gray strings and strings recursively constructed from short input strings are examples.

For completeness, consider the following problem: given a number $k \le 10^5$ and a string of length $\le 10^5$, denoted $s$, compute the number of occurrences of $s$ in the $k$-th Gray string. Recall that Gray strings are defined as follows:

Because of its astronomical length, even constructing $t$ is impossible here: the $k$-th Gray string has $2^k - 1$ characters. However, its final prefix-function value can be computed efficiently if only a few prefix-function values at the beginning are known.

In addition to the automaton, compute $G[i][j]$, the automaton state after starting from state $j$ and processing $g_i$, and $K[i][j]$, after starting from state $j$ and processing $g_i$, the number of occurrences of $s$ in $g_i$. In fact, $K[i][j]$ is the number of times the prefix function takes the value $|s|$ during the operation. The answer is $K[k][0]$.

How should these values be computed? By definition, the initial conditions are $G[0][j] = j$ and $K[0][j] = 0$. All subsequent values can be obtained from earlier values and the automaton. To compute the values for a particular $i$, recall that $g_i$ is the concatenation of $g_{i - 1}$, the $i$-th character of the alphabet, and $g_{i - 1}$. Thus the automaton passes through the following states:

The value of $K[i][j]$ can be computed similarly.

Here, $[\cdot]$ is $1$ when its expression is true and $0$ otherwise. In summary, this solves the Gray-string problem and a large class of similar problems. For example, the same method solves the following problem: given a string $s$ and a collection of patterns $t_i$, each pattern consists of ordinary characters and may recursively insert previously defined strings in the form $t_{k}^{\text{cnt}}$, meaning that $t_k$ must be inserted $\text{cnt}$ times at that position. Here is an example of such patterns:

Recursive substitution makes the string lengths grow explosively; they can even reach an order of magnitude of $100^{100}$. We need to find the number of occurrences of string $s$ in each string.

This problem can likewise be solved by constructing a prefix-function automaton. As before, use previously computed results to calculate the transitions for each pattern and then count the answers.

Exercises

• UVa 455 "Periodic Strings"
• UVa 11022 "String Factoring"
• UVa 11452 "Dancing the Cheeky-Cheeky"
• UVa 12604 - Caesar Cipher
• UVa 12467 - Secret Word
• UVa 11019 - Matrix Matcher
• SPOJ - Pattern Find
• Codeforces - Anthem of Berland
• Codeforces - MUH and Cube Walls

References and Notes

This page was mainly translated from the article Префикс-функция. Алгоритм Кнута-Морриса-Пратта and its English translation Prefix function. Knuth–Morris–Pratt algorithm. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.