Skip to content

Prefix Function & KMP Algorithm

Definitions of String Prefix and Suffix

For definitions of string prefix, proper prefix, suffix, and proper suffix, refer to String Basics.

Prefix Function

Definition

Given a string \(s\) of length \(n\), its prefix function is defined as an array \(\pi\) of length \(n\). Here \(\pi[i]\) is defined as:

  1. If the substring \(s[0\dots i]\) has an equal proper prefix and proper suffix: \(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), i.e., \(\pi[i]=k\);
  2. If there is more than one such pair, then \(\pi[i]\) is the length of the longest one;
  3. If there is no such pair, then \(\pi[i]=0\).

Simply put, \(\pi[i]\) is the length of the longest equal proper prefix and proper suffix of the substring \(s[0\dots i]\).

In mathematical terms:

\[ \pi[i] = \max_{k = 0 \dots i}\{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]\} \]

Specifically, it is defined that \(\pi[0]=0\).

Process

For example, for the string abcabcd,

\(\pi[0]=0\), because a has no proper prefix and proper suffix, defined as 0 by convention.

\(\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 only one pair of equal proper prefix and proper suffix: a, of length 1.

\(\pi[4]=2\), because abcab has only ab as equal proper prefix and proper suffix, of length 2.

\(\pi[5]=3\), because abcabc has only abc as equal proper prefix and proper suffix, of length 3.

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

Similarly, the prefix function for the string aabaaab can be computed as \([0, 1, 0, 1, 2, 2, 3]\).

Naive Algorithm for Computing the Prefix Function

Process

A straightforward algorithm to compute the prefix function according to the definition:

  • In a loop, compute the prefix function values \(\pi[i]\) for \(i = 1\to n - 1\) (with \(\pi[0]\) assigned as \(0\)).
  • To compute the current prefix function value \(\pi[i]\), we let variable \(j\) start from the largest possible proper prefix length \(i\).
  • If the proper prefix and proper suffix of current length are equal, then the length is \(\pi[i]\); otherwise, decrement \(j\) by 1 and continue matching until \(j=0\).
  • If \(j = 0\) and no match is found, set \(\pi[i] = 0\) and move to the next index \(i + 1\).
Implementation

The specific implementation is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// 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;
}

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

Clearly, the time complexity of this algorithm is \(O(n^3)\), leaving much room for improvement.

Efficient Algorithm for Computing the Prefix Function

First Optimization

The first important observation is that adjacent prefix function values increase by at most \(1\).

Refer to the diagram below: when trying to maximize \(\pi[i+1]\), the newly added character \(s[i+1]\) must match the corresponding character, i.e., \(s[i+1]=s[\pi[i]]\), in which case \(\pi[i+1] = \pi[i]+1\).

\[ \underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i] = 3} ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i] = 3} ~ s_{i+1}}_{\pi[i+1] = 4} \]

Therefore, when moving to the next position, the prefix function value either increases by one, stays the same, or decreases.

Implementation

The improved algorithm is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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 preliminary improved algorithm, when computing each \(\pi[i]\), the best case is when the first string comparison completes the match, meaning the base number of string comparisons is n-1.

Due to the limit j = pi[i-1]+1 (pi[0]=0) on the maximum number of string comparisons, we can see that only in the best case does the upper bound of string comparisons accumulate by 1, while each extra string comparison consumes future growth space.

Thus, we can derive the worst-case scenario for string comparisons: at least 1 string comparison is consumed, and at most n-2 comparisons are accumulated, resulting in n-1 + n-2 = 2n-3 string comparisons.

After this optimization, computing the prefix function requires only \(O(n)\) string comparisons, reducing the total complexity to \(O(n^2)\).

Second Optimization

In the first optimization, we discussed the best case for computing \(\pi[i+1]\): \(s[i+1]=s[\pi[i]]\), in which case \(\pi[i+1] = \pi[i]+1\). Now let's go further along this line: discuss how to jump when \(s[i+1] \neq s[\pi[i]]\).

As shown in the figure above, when a mismatch occurs, we want to find the second longest length \(j\) for the substring \(s[0\dots i]\), after \(\pi[i]\), such that the prefix property at position \(i\) still holds, i.e., \(s[0 \dots j - 1] = s[i - j + 1 \dots i]\):

\[ \overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1} \]

If we find such a length \(j\), we only need to compare \(s[i + 1]\) and \(s[j]\) again. If they are equal, then \(\pi[i + 1] = j + 1\). Otherwise, we need to find the second longest length \(j^{(2)}\) for substring \(s[0\dots i]\), after \(j\), such that the prefix property holds, and so on, until \(j = 0\). If \(s[i + 1] \neq s[0]\), then \(\pi[i + 1] = 0\). The second comparison is illustrated below.

Observing the figure above, because \(s[0\dots \pi[i]-1] = s[i-\pi[i]+1\dots i]\), for the second length \(j\) of \(s[0\dots i]\), we have the property:

\[ s[0 \dots j - 1] = s[i - j + 1 \dots i]= s[\pi[i]-j\dots \pi[i]-1] \]

This formula is illustrated below:

That is, \(j\) is equivalent to the prefix function value of substring \(s[\pi[i]-1]\), corresponding to the lower part of the figure above, i.e., \(j=\pi[\pi[i]-1]\). Similarly, the second length after \(j\) is equivalent to the prefix function value of \(s[j-1]\), \(j^{(2)}=\pi[j-1]\).

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

Final Algorithm

Thus, we can finally construct an algorithm that requires no string comparisons and performs only \(O(n)\) operations.

Moreover, the implementation of this algorithm is surprisingly short and intuitive:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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, meaning it processes data as it arrives—for example, you can read the string character by character and immediately compute the prefix function value for each character. The algorithm still needs to store the string itself and previously computed prefix function values, but if we already know the maximum possible value \(M\) of the prefix function for the string, we only need to store the first \(M + 1\) characters of the string and their corresponding prefix function values.

Applications

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

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

Process

Given a text \(t\) and a string \(s\), we try to find and display all occurrences of \(s\) in \(t\).

For simplicity, let \(n\) denote the length of string \(s\), and \(m\) denote the length of text \(t\).

We construct a string \(s + \# + t\), where \(\#\) is a separator that does not appear in \(s\) or \(t\). Then compute the prefix function of this string. Now consider the meaning of the prefix function values after the first \(n + 1\) values (i.e., those belonging to the string \(s\) and the separator). By definition, \(\pi[i]\) is the length of the longest proper substring that ends at \(i\) and is also a prefix. In our case, its value is the length of the longest substring ending at \(i\) that is equal to a prefix of \(s\). Due to the separator, this length cannot exceed \(n\). If the equality \(\pi[i] = n\) holds, it means \(s\) appears completely at that position (i.e., its right endpoint is at position \(i\)). Note that this index refers to the string \(s + \# + t\).

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

As mentioned in the computation of the prefix function, if we know that the prefix function values never exceed a certain value, we do not need to store the entire string and the entire prefix function, but only the beginning part of both. In our case, this means we only need to store the string \(s + \#\) and the corresponding prefix function values. We can read the characters of string \(t\) one by one and compute the prefix function value at the current position.

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

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

Period of a String

For a string \(s\) and \(0 < p \le |s|\), if \(s[i] = s[i+p]\) holds for all \(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 length \(r\) and the suffix of length \(r\) of \(s\) are equal, then the prefix of length \(r\) is called a border of \(s\).

Having a border of length \(r\) for \(s\) implies that \(|s|-r\) is a period of \(s\).

According to the definition of the prefix function, we can obtain all border lengths of \(s\), i.e., \(\pi[n-1],\pi[\pi[n-1]-1], \ldots\).[^ref1]

Thus, all periods of \(s\) can be computed in \(O(n)\) time using the prefix function. Since \(\pi[n-1]\) is the length of the longest border of \(s\), \(n - \pi[n-1]\) is the minimum period of \(s\).

Counting Occurrences of Each Prefix

In this section, we will discuss two problems simultaneously. Given a string \(s\) of length \(n\), in the first variant we want to count the number of occurrences of each prefix \(s[0 \dots i]\) in the same string, and in the second variant we want to count the number of occurrences of each prefix \(s[0 \dots i]\) in another given string \(t\).

First, let's solve the first problem. Consider the prefix function value \(\pi[i]\) at position \(i\). By definition, it means that a prefix of \(s\) of length \(\pi[i]\) appears at position \(i\) with \(i\) as the right endpoint, and no longer prefix satisfies this definition. Meanwhile, shorter prefixes may also end at this position. It is easy to see that we encounter a problem 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\)? This length must also be a suffix ending at \(i\). Therefore, at position \(i\) as the right endpoint, 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.

Implementation 
1
2
3
4
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]++;

1
2
3
4
5
6
7
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 above code, we first count how many times each prefix function value appears in the array \(\pi\), then compute the final answer: if we know that a prefix of length \(i\) appears exactly \(\text{ans}[i]\) times, then 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 prefixes, we add \(1\) to each result.

Now consider the second problem. We apply the trick from Knuth–Morris–Pratt: construct a string \(s + \# + t\) and compute its prefix function. The only difference from the first problem is that we only care about prefix function values related to string \(t\), i.e., \(\pi[i]\) for \(i \ge n + 1\). With these values, we can apply the same algorithm as in the first problem.

Number of Distinct Substrings in a String

Given a string \(s\) of length \(n\), we want to compute the number of its distinct substrings.

We will solve this problem iteratively. In other words, knowing the current number of distinct substrings, we want to find a way to recompute this number after appending a character to the end of \(s\).

Let \(k\) be the current number of distinct substrings of \(s\). We append a new character \(c\) to \(s\). Obviously, some new substrings ending with character \(c\) will appear. We want to count those substrings ending with this character that we have not encountered before.

Construct the string \(t = s + c\) and reverse it to get \(t^{\sim}\). Now our task becomes counting how many prefixes of \(t^{\sim}\) do not appear anywhere else in \(t^{\sim}\). If we compute the maximum prefix function value \(\pi_{\max}\) of \(t^{\sim}\), then the longest prefix that appears in \(s\) has length \(\pi_{\max}\). Naturally, all shorter prefixes also appear.

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

So for each added character, we can compute the number of new substrings in \(O(n)\) time, resulting in a final complexity of \(O(n^2)\).

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

String Compression

Given a string \(s\) of length \(n\), we want to find its shortest "compressed" representation, i.e., we want to find the shortest string \(t\) such that \(s\) can be represented as the concatenation of one or more copies of \(t\).

Obviously, we only need to find the length of \(t\). Knowing this length, the answer is the prefix of \(s\) of that length.

Let's compute the prefix function of \(s\). Using the last value \(\pi[n - 1]\), we define \(k = n - \pi[n - 1]\). We will prove that if \(k\) divides \(n\), then \(k\) is the answer; otherwise, no valid compression exists, so the answer is \(n\).

Assume \(n\) is divisible by \(k\). Then the string can be divided into blocks of length \(k\). According to the definition of the prefix function, the prefix of length \(n - k\) equals its suffix. But this means the last block equals the second last block, the second last block equals the third last block, and so on. As a result, all blocks are equal, so we can compress the string \(s\) to length \(k\).

Proof

Indeed, we still need to prove that this value is optimal. Actually, if there is a compressed representation shorter than \(k\), then the last prefix function value \(\pi[n - 1]\) must be greater than \(n - k\). Therefore, \(k\) is the answer.

Now assume \(n\) is not divisible by \(k\). We will prove by contradiction that the answer is \(n\)1. Suppose the minimal compressed representation \(r\) has length \(p\) (\(p\) divides \(n\)), and string \(s\) is divided into \(n / p \ge 2\) blocks. Then the last prefix function value \(\pi[n - 1]\) must be greater than \(n - p\) (if equal, then \(n\) would be divisible by \(k\)), meaning the suffix it represents partially covers the first block. Now consider the second block of the string. This block has two interpretations: the first as \(r_0 r_1 \dots r_{p - 1}\), and the second as \(r_{p - k} r_{p - k + 1} \dots r_{p - 1} r_0 r_1 \dots r_{p - k - 1}\). Since both interpretations correspond to the same string, we obtain a system of \(p\) equations, which can be simplified as \(r_{(i + k) \bmod p} = r_{i \bmod p}\), where \(\cdot \bmod p\) denotes the least non-negative residue modulo \(p\).

\[ \begin{gathered} \overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 ~ r_5}^p ~ \overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 r_5}^p \\ r_0 ~ r_1 ~ r_2 ~ r_3 ~ \underbrace{\overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 ~ r_5}^p ~ r_0 ~ r_1}_{\pi[11] = 8} \end{gathered} \]

According to the extended Euclidean algorithm, we can find integers \(x\) and \(y\) such that \(xk + yp = \gcd(k, p)\). By appropriately combining with the identity \(pk - kp = 0\), we can obtain \(x' > 0\) and \(y' < 0\) such that \(x'k + y'p = \gcd(k, p)\). This means that by repeatedly applying the equations from the system, we obtain a new system \(r_{(i + \gcd(k, p)) \bmod p} = r_{i \bmod p}\).

Since \(\gcd(k, p)\) divides \(p\), this means \(\gcd(k, p)\) is a period of \(r\). Because \(\pi[n - 1] > n - p\), we have \(n - \pi[n - 1] = k < p\), so \(\gcd(k, p)\) is a period of \(r\) smaller than \(p\). Therefore, string \(s\) has a compressed representation of length \(\gcd(k, p) < p\), contradicting the minimality of \(p\).

In conclusion, there is no compressed representation shorter than \(k\), so the answer is \(k\).

Building an Automaton Based on the Prefix Function

Let's return to the new string formed by concatenating two strings with a separator. For strings \(s\) and \(t\), we compute the prefix function of \(s + \# + t\). Obviously, because \(\#\) is a separator, the prefix function value never exceeds \(|s|\). Therefore, we only need to store the string \(s + \#\) and its corresponding prefix function values, and then we can dynamically compute the prefix function values for all subsequent characters:

\[ \underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{need to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{do not need to store}} \]

Actually, in this case, knowing the next character \(c\) of \(t\) and the previous prefix function value is sufficient to compute the next prefix function value, without needing any other characters of \(t\) or their corresponding prefix function values.

In other words, we can construct an automaton (a finite state machine): its states are the current prefix function values, and transitions from one state to another are determined by the next character.

Therefore, even without the string \(t\), we can apply the algorithm for constructing the transition table to build a transition table \(( \text { old } \pi , c ) \rightarrow \text { new } _ { - } \pi\):

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
  }
}

However, in this form, for a lowercase alphabet, the time complexity is \(O(|\Sigma|n^2)\). Note that we can apply dynamic programming to reuse already computed parts of the table. Whenever we change from value \(j\) to \(\pi[j - 1]\), we are essentially saying that the state reached by transition \((j, c)\) is the same as that reached by transition \((\pi[j - 1], c)\), but we have already computed that answer precisely.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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]);
    }
  }
}

Finally, we can construct the automaton in \(O(|\Sigma|n)\) time.

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

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

By building the automaton for \(s + \#\), we no longer need to store the string \(s\) and its corresponding prefix function values. All transitions are already computed in the table.

But besides that, there is a second, less direct application. We can use this automaton to accelerate computation when string \(t\) is some huge string constructed by certain rules. Examples include Gray strings, or strings constructed recursively from shorter input strings.

For completeness, let's solve such a problem: given a number \(k \le 10^5\), and a string \(s\) of length \(\le 10^5\), we need to compute the number of occurrences of \(s\) in the \(k\)-th Gray string. Recall that Gray strings are defined as follows:

\[ \begin{aligned} g_1 &= \mathtt{a}\\ g_2 &= \mathtt{aba}\\ g_3 &= \mathtt{abacaba}\\ g_4 &= \mathtt{abacabadabacaba} \end{aligned} \]

Due to their astronomical lengths, constructing string \(t\) is impossible in this case: the \(k\)-th Gray string has \(2^k - 1\) characters. However, we can efficiently compute the prefix function value at the end of the string by knowing only a few initial prefix function values.

Besides the automaton, we also need to compute values \(G[i][j]\): the state of the automaton after processing \(g_i\) starting from state \(j\), and values \(K[i][j]\): the number of occurrences of \(s\) in \(g_i\) when starting from state \(j\). Actually, \(K[i][j]\) is the number of times the prefix function takes the value \(|s|\) during the operation. The answer to the problem is clearly \(K[k][0]\).

How do we compute these values? First, by definition, the initial conditions are \(G[0][j] = j\) and \(K[0][j] = 0\). All subsequent values can be computed from previous values using the automaton. To compute the values for some \(i\), recall that string \(g_i\) is the concatenation of \(g_{i - 1}\), the \(i\)-th character of the alphabet, and \(g_{i - 1}\). Therefore, the automaton goes through the following states:

\[ \begin{gathered} \text{mid} = \text{aut}[G[i - 1][j]][i] \\ G[i][j] = G[i - 1][\text{mid}] \end{gathered} \]

The value of \(K[i][j]\) can also be computed simply.

\[ K[i][j] = K[i - 1][j] + [\text{mid} == |s|] + K[i - 1][\text{mid}] \]

where \([\cdot]\) is \(1\) if the expression is true, otherwise \(0\). In summary, we can now solve the problem about Gray strings and a large class of similar problems. For example, the same method can solve the following problem: given a string \(s\) and some patterns \(t_i\), where each pattern is given as follows: the pattern consists of ordinary characters, possibly with recursive insertions of previous strings in the form \(t_{k}^{\text{cnt}}\), meaning at that position we must insert string \(t_k\) \(\text{cnt}\) times. Here is an example of such patterns:

\[ \begin{aligned} t_1 &= \mathtt{abdeca} \\ t_2 &= \mathtt{abc} + t_1^{30} + \mathtt{abd} \\ t_3 &= t_2^{50} + t_1^{100} \\ t_4 &= t_2^{10} + t_3^{100} \end{aligned} \]

Recursive substitution causes string lengths to explode, reaching magnitudes like \(100^{100}\). Yet we must find the number of occurrences of string \(s\) in each string.

This problem can also be solved by constructing a prefix function automaton. As before, we compute transitions for each pattern using previously computed results and count the answer accordingly.

Practice Problems

References and Notes

**This page is mainly translated from the blog post [Префикс-функция. Алгоритм Кнута-Морриса-Пратта

  1. In the Russian and English versions, this part of the proof appears to be erroneous. This part of the proof in this article is added by the author. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用