This lecture uses 0-based indexing: the first character has index 0, and the last has index n−1.
Many string problems ask whether the beginning of a string appears again somewhere else. It may appear as a full pattern, as a border, or as part of a repeated structure. The Z-function stores exactly this information for every starting position.
For each position i, we ask one simple question: if we start reading the string from i, how many first characters are equal to the prefix of the whole string?
For example, in the string abacaba, the substring beginning at position is . It matches the first three characters of the string, so .
4
aba
z[4]=3
The Z-function belongs to the same family of ideas as the prefix function, but looks at matches from another direction. The prefix function describes a prefix that ends at each position. The Z-function describes a prefix that starts at each position.
Problem and 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, if p is aba and t is abacaba, the pattern starts at positions 0 and 4.
To turn this into a prefix-matching problem, we join the strings:
aba#abacaba
Here # is a separator that does not occur in either string. Now every occurrence of aba in the text becomes a position where the suffix of the joined string begins with the complete prefix aba. If we can quickly calculate the prefix-match length from every position, all occurrences become easy to recognize.
Naive approach
For every position i of a string s, we can start with z[i]=0 and compare characters from left to right:
compare s[0] with s[i];
if they are equal, compare s[1] with s[i+1];
continue until the characters differ or the string ends.
This directly calculates the correct value. However, it forgets everything learned at earlier positions and may compare the same characters many times.
Consider a string consisting only of a. From position 1, we compare almost the whole string. From position 2, we again compare almost the whole string, and so on. The total number of comparisons is 1+2+⋯+(n−1), which is O(n2).
The linear algorithm performs the same kind of comparisons, but reuses information from a segment that is already known to match the prefix.
The slow implementation is almost a direct translation of the definition:
This code is useful because the efficient algorithm keeps the same while loop. The only new idea is to choose a better starting value for z[i] before that loop begins.
Core concept
Let s be a string of length n. For every position i>0, z[i] is the largest length k such that the prefix s[0…k−1] is equal to the substring s[i…i+k−1]. Formally, z[i]=max{k∣s[0…k−1]=s[i…i+k−.
If the first characters are already different, then z[i]=0. We use z[0]=0 by convention because comparing the entire string with itself is not useful for the algorithm.
For abacaba, the Z-function is:
[0, 0, 1, 0, 3, 0, 1]
The most important value is z[4]=3 because aba, starting from position 4, is equal to the prefix aba. At position 2, only the first character matches, so z[2]=1.
Z-block and reuse of old values
The substring s[i…i+z[i]−1] is called the Z-block starting at i. It is exactly the part beginning at i that matches the prefix.
While scanning the string from left to right, we maintain one Z-block [l,r] with the following property:
s[l…r] is equal to s[0…r−l].
In other words, this block is a copy of the prefix. Among all Z-blocks found so far, we keep the one that reaches farthest to the right. In this lecture, r is the inclusive last position of the block.
Now suppose the current position i lies inside this segment. Since the segment is a copy of the prefix, position i inside the segment corresponds to position i−l inside the prefix.
We already know z[i−l], so we can reuse it. However, the current segment only guarantees equality up to r. Therefore, the safe initial value is
z[i]=min(z[i−l],r−i+1)
The term r−i+1 is the number of characters remaining in the current segment. We must take the minimum because z[i−l] may describe a match that continues beyond the part we have already proved equal.
After copying this safe value, we compare characters normally starting from the first unknown position. If the match continues beyond r, we extend the rightmost segment.
If i>r, then the current position is outside the known segment. There is nothing to reuse, so we begin with z[i]=0 and compare characters directly.
[VISUAL IDEA: place the prefix above the current Z-block, connect position i with position i-l, and highlight that only the part ending at r can be copied safely]
Main algorithm
Assume that we have already calculated the Z-values for positions 0…i−1. We now want to find z[i]. There are two cases.
Case 1: i>r
The position is outside the rightmost Z-block, so the earlier block tells us nothing about the match beginning here. We start with z[i]=0 and compare s[z[i]] with s[i+z[i]] until the characters differ or the string ends.
If this new match reaches farther than the old block, its boundaries become l=i and r=i+z[i]−1.
Case 2: i≤r
The position lies inside the rightmost Z-block. Since s[l…r] is a copy of the prefix, position i corresponds to position i−l in the prefix. We already know the match length z[i−l] there.
However, the current block proves equality only until r. There are r−i+1 known characters left, so we begin with
z[i]=min(z[i−l],r−i+1)
If this copied match ends before r, no new comparisons are needed: the mismatch that stopped z[i−l] appears in the same place here. If the copied match reaches r, the real match may continue farther, so we return to direct comparison from the first character after the known block.
In both cases, whenever [i,i+z[i]−1] reaches farther than the current r, it becomes the new rightmost Z-block.
For pattern matching, we calculate the Z-function of p + '#' + t. A position belongs to an occurrence exactly when its Z-value is equal to the pattern length.
Algorithm:
The important difference from the naive algorithm is that comparisons inside a known Z-block are replaced by one array lookup. Successful new comparisons move the right boundary to the right, and it can move at most n times. There can also be at most one final failed comparison for each position. Therefore, the complete Z-function is calculated in O(n) time.
Applications
Pattern matching
Let the pattern be aba and the text be abacaba. We build:
aba#abacaba
The text begins at position 4 of the joined string. At joined positions 4 and 8, the Z-value is 3, equal to the pattern length. Converting them back to text positions gives:
4−3−1=0;
8−3−1=4.
Therefore, the pattern occurs in the text at positions 0 and 4.
The separator is important. It prevents a prefix match from crossing from the pattern into the text and makes the two parts unambiguous.
Shortest repeating block
Suppose we want to find the shortest string whose copies form the whole string s. For example, abcabcabc consists of three copies of abc, so its shortest repeating block has length 3.
Let a candidate block length be k. First, k must divide n; otherwise, whole blocks cannot fill the string. We also need everything after the first block to repeat the prefix. The value z[k] tells us how many characters match after shifting the string by k positions, so the required condition is
z[k]=n−k
or equivalently,
k+z[k]=n
We check the divisors of n from smallest to largest and take the first one that satisfies this condition. If no proper divisor works, the answer is n, because every string is one copy of itself.
For abcabcabc, n=9 and z[3]=6. Since 3 divides 9 and 3+z[3]=9, the answer is 3.
Implementation
The input contains a pattern p and a text t, each without spaces. The program prints the number of occurrences and then their 0-indexed starting positions.
Complexity
Z-function:O(n) time and O(n) memory for a string of length n.
Pattern matching:O(∣p∣+∣t∣) time and O(∣p∣+∣t∣) memory.
Shortest repeating block:O(n) time and O(n) memory.
1]}
1. Define function z_function(s):
1.1. Let n = length of s.
1.2. Create z[0..n-1] filled with 0.
1.3. Set l = 0 and r = -1.
1.4. For i = 1..n-1:
1.4.1. If i <= r, set z[i] = min(z[i-l], r-i+1).
1.4.2. While i+z[i] < n and s[z[i]] == s[i+z[i]]:
1.4.2.1. Increase z[i] by 1.
1.4.3. If z[i] > 0 and i+z[i]-1 > r:
1.4.3.1. Set l = i.
1.4.3.2. Set r = i+z[i]-1.
1.5. Return z.
2. Read pattern p and text t.
3. Let s = p + "#" + t.
4. Calculate z = z_function(s).
5. For every position i belonging to the text part of s:
5.1. If z[i] == length of p, add i-length(p)-1 to the answer.
6. Output all positions in the answer.
vector<int> z_function_slow(const string &s){ int n = s.size(); 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;}
#include <bits/stdc++.h>using namespace std;vector<int> z_function(const string &s){ int n = s.size(); vector<int> z(n); int l = 0; int r = -1; for(int i = 1; i < n; i++){ if(i <= r){ z[i] = min(z[i - l], r - i + 1);} while(i + z[i]< n && s[z[i]] == s[i + z[i]]){ z[i]++;} if(z[i]> 0 && i + z[i] - 1> r){ l = i; r = i + z[i] - 1;}} return z;}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> z = z_function(s); vector<int> ans; for(int i = m + 1; i <(int)s.size(); i++){ if(z[i] == m){ ans.push_back(i - m - 1);}} cout << ans.size()<< endl; for(int x : ans){ cout << x << ' ';} cout << endl; return 0;}