Skip to content

Z-function (Extended KMP)

Convention: string indices start from \(0\).

Definition

For a string \(s\) of length \(n\), define the function \(z[i]\) as the length of the longest common prefix (LCP) between \(s\) and \(s[i,n-1]\) (the suffix starting at \(s[i]\)). Then \(z\) is called the Z-function of \(s\). In particular, \(z[0] = 0\).

Internationally, the algorithm computing this array is generally called the Z Algorithm, while in China it is often referred to as Extended KMP (exKMP).

This article introduces an algorithm to compute the Z-function in \(O(n)\) time complexity and its various applications.

Explanation

The following examples show the Z-function for different strings:

  • \(z(\mathtt{aaaaa}) = [0, 4, 3, 2, 1]\)
  • \(z(\mathtt{aaabaab}) = [0, 2, 1, 0, 2, 1, 0]\)
  • \(z(\mathtt{abacaba}) = [0, 0, 1, 0, 3, 0, 1]\)

Naive Algorithm

The naive algorithm for the Z-function has complexity \(O(n^2)\):

Implementation 
1
2
3
4
5
6
7
vector<int> z_function_trivial(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1; i < n; ++i)
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
  return z;
}

1
2
3
4
5
6
7
def z_function_trivial(s):
    n = len(s)
    z = [0] * n
    for i in range(1, n):
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
    return z

Linear Algorithm

Like most algorithms in string topics, the key lies in applying automaton thinking to find state transition functions under constraints, allowing us to accelerate the computation of new states using previous states.

In this algorithm, we compute \(z[i]\) sequentially from \(1\) to \(n-1\) (with \(z[0]=0\)). While computing \(z[i]\), we utilize the already computed values \(z[0],\ldots,z[i-1]\).

For \(i\), we call the interval \([i,i+z[i]-1]\) the matching segment of \(i\), also known as a Z-box.

During the algorithm, we maintain the matching segment with the rightmost endpoint. For convenience, denote it as \([l,r]\). By definition, \(s[l,r]\) is a prefix of \(s\). While computing \(z[i]\), we ensure \(l\le i\). Initially, \(l=r=0\).

During the computation of \(z[i]\):

  • If \(i\le r\), then by the definition of \([l,r]\), we have \(s[i,r] = s[i-l,r-l]\), so \(z[i]\ge \min(z[i-l],r-i+1)\). Then:
    • If \(z[i-l] < r-i+1\), then \(z[i] = z[i-l]\).
    • Otherwise, \(z[i-l]\ge r-i+1\). In this case, we set \(z[i] = r-i+1\), then brute-force extend \(z[i]\) character by character until it cannot be extended.
  • If \(i>r\), we directly apply the naive algorithm, starting from \(s[i]\) to compute \(z[i]\) by brute force.
  • After obtaining \(z[i]\), if \(i+z[i]-1>r\), we need to update \([l,r]\), i.e., set \(l=i, r=i+z[i]-1\).

You can visit this website to see a simulation of the Z-function.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r and z[i - l] < r - i + 1:
            z[i] = z[i - l]
        else:
            z[i] = max(0, r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

Complexity Analysis

For the inner while loop, each execution moves \(r\) forward by at least \(1\) position, and \(r< n-1\), so it executes at most \(n\) times in total.

The outer loop is a single linear traversal.

Total complexity is \(O(n)\).

Applications

Let's now consider applications of the Z-function in several specific scenarios.

These applications are largely similar to those of the prefix function.

Matching All Substrings

To avoid confusion, let \(t\) be the text and \(p\) be the pattern. The problem is: find all occurrences of pattern \(p\) in text \(t\).

To solve this, we construct a new string \(s = p + \diamond + t\), i.e., we concatenate \(p\) and \(t\) but place a separator character \(\diamond\) between them (we choose \(\diamond\) such that it definitely does not appear in \(p\) or \(t\)).

First, compute the Z-function of \(s\). Then, for any \(i\) in the interval \([0,|t| - 1]\), consider the Z-function value \(k = z[i + |p| + 1]\) of the suffix starting at \(t[i]\) in \(s\). If \(k = |p|\), then we know there is an occurrence of \(p\) starting at position \(i\) in \(t\); otherwise, there is no such occurrence.

The time complexity (and also space complexity) is \(O(|t| + |p|)\).

Number of Distinct Substrings

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

Consider computing incrementally: knowing the current number of distinct substrings of \(s\), compute the 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 the end of \(s\). Obviously, some new substrings ending with \(c\) will appear (those ending with \(c\) that have not appeared before).

Let string \(t\) be the reverse of \(s + c\) (reverse means the string formed by reversing the order of characters). Our task is to compute how many prefixes of \(t\) do not appear elsewhere in \(t\). Consider computing the Z-function of \(t\) and finding its maximum value \(z_{\max}\). Then the reverses of prefixes of \(t\) with length less than or equal to \(z_{\max}\) are substrings ending with \(c\) that have already appeared in \(s\).

Thus, the number of new substrings appearing after adding character \(c\) to \(s\) is \(|t| - z_{\max}\).

The algorithm's time complexity is \(O(n^2)\).

Notably, we can use the same method to recompute the number of distinct substrings in \(O(n)\) time after adding or deleting a character at an endpoint (from the tail or head).

String Period

Given a string \(s\) of length \(n\), find its shortest period, i.e., find the shortest string \(t\) such that \(s\) can be represented as a concatenation of several copies of \(t\).

Consider computing the Z-function of \(s\). Then the length of its period is the smallest divisor \(i\) of \(n\) satisfying \(i+z[i]=n\).

The proof of this fact is similar to the proof using the prefix function.

Practice Problems

This page is mainly translated from the blog post Z-функция строки и её вычисление and its English translation Z-function and its calculation. The Russian version's license is Public Domain + Leave a Link; the English version's license is CC-BY-SA 4.0.

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