Z Function (Extended KMP)

Convention: string indices start at $0$.

Definition

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

The algorithm for computing this array is generally called the Z algorithm internationally, while in China it is called extended KMP (exKMP).

This article introduces an $O(n)$-time algorithm for computing the Z function and its 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 Z-function algorithm has complexity $O(n^2)$:

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;
}

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

As in many string algorithms, the key is to use the automaton idea to find a state-transition function under the relevant constraints, so that previously computed states can accelerate new computations.

In this algorithm, we compute $1$ sequentially from $n-1$ to $z[i]$ ($z[0]=0$). When computing $z[i]$, we use 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 right endpoint. Denote it by $[l,r]$. By definition, $s[l,r]$ is a prefix of $s$. When computing $z[i]$, we maintain $l\le i$. Initially, $l=r=0$.

When computing $z[i]$:

• If $i\le r$ $[l,r]$ $s[i,r] = s[i-l,r-l]$ $z[i]\ge \min(z[i-l],r-i+1)$ $z[i-l] < r-i+1$ $z[i] = z[i-l]$ $z[i-l]\ge r-i+1$ $z[i] = r-i+1$ $z[i]$ $i>r$ $s[i]$ $z[i]$ $z[i]$ $i+z[i]-1>r$ $[l,r]$ $l=i, r=i+z[i]-1$, then by the definition of , , so . Then:
  • If , set .
  • Otherwise . Set , then compare subsequent characters directly to extend as far as possible.
• If , compute directly by comparing from , as in the naive algorithm.
• After computing , if , update by setting and .

Visit this website to see a simulation of the Z function.

Implementation

C++

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;
}

Python

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

Each execution of the inner while loop moves $r$ $1$ $r< n-1$ $n$ forward by at least one position. Since , it executes at most times in total.

The outer loop makes only one linear pass.

The total complexity is $O(n)$.

Applications

We now consider applications of the Z function in several concrete settings.

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

Matching all occurrences

To avoid confusion, call $t$ the text and $p$ the pattern. The problem is to find every occurrence of pattern $t$ in text $p$.

To solve this problem, construct $s = p + \diamond + t$ $p$ $t$ $\diamond$ $\diamond$ $p$ $t$: concatenate and with a separator between them, chosen so that it occurs in neither nor .

First compute the Z function of $s$ $[0,|t| - 1]$ $i$ $t[i]$ $s$ $k = z[i + |p| + 1]$ $k = |p|$ $p$ $t$ $i$ $p$ $t$ $i$. For any in , consider the Z value in for the suffix beginning at . If , an occurrence of starts at position in ; otherwise no occurrence starts there.

Its time complexity, which is also its space complexity, is $O(|t| + |p|)$.

Number of distinct substrings

Given a string $n$ of length $s$, compute the number of distinct substrings of $s$.

Consider the increment: knowing the current number of distinct substrings of $s$, compute the number 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 the end of $s$. Clearly, some new substrings ending in $c$ appear; these are substrings ending in $c$ that did not occur before.

Let $t$ be the reverse of $s + c$. We need to count how many prefixes of $t$ do not occur elsewhere in $t$. Compute the Z function of $t$ and let its maximum be $z_{\max}$. The reverses of prefixes of $t$ with length at most $z_{\max}$ are substrings ending in $s$ that already occurred in $c$.

Therefore, the number of new substrings after appending $c$ to $s$ is $|t| - z_{\max}$.

The algorithm has time complexity $O(n^2)$.

Notably, the same method can recompute the number of distinct substrings in $O(n)$ time after adding a character at an endpoint or deleting one from either the end or the beginning.

String periods

Given a string $n$ of length $s$, find its shortest full period: the shortest string $t$ such that $s$ can be represented as a concatenation of copies of $t$.

Compute the Z function of $s$. The length of its full period is the smallest divisor $n$ of $i$ satisfying $i+z[i]=n$.

The proof is the same as the proof for the corresponding application of the prefix function.

Practice problems

• Luogu P5410 (https://www.luogu.com.cn/problem/P5410) extended KMP/exKMP (Z function)
• Luogu P7114 (https://www.luogu.com.cn/problem/P7114) string matching
• CF126B Password
• UVa # 455 Periodic Strings
• UVa # 11022 String Factoring
• UVa 11475 - Extend to Palindrome
• Codechef - Chef and Strings
• Codeforces - Prefixes and Suffixes
• Leetcode 2223 - Sum of Scores of Built Strings

This page is mainly translated from Z-function of a string and its computation and its English translation Z-function and its calculation. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.