Given two strings, one is a text string, text, and the other is a pattern string, pattern. Print the indexes of all occurrences of the pattern string in the text string using the Z function algorithm. Use 0-based indexing while returning the indices.
Input: text = "xyzabxyzabxyz", pattern = "xyz"
Output: 0 5 10
Expalanation : The pattern "xyz" occurs three times in text, starting at indices 0, 5, and 10.
Input: text = "cabcdab", pattern = "abc"
Output: 1
Expalanation : The pattern "abc" occurs one time in text, starting at index 1.
Input: text = "aaabaaaabaaa", pattern = "aa"
Before going to the Intution, let's first understand what is Z-algorithm.
The Z-algorithm is a common technique to solve String Pattern Matching problems.
It combines the pattern P and the text T as P+"$"+T, computes the Z-array, and find matches.
Z[i] represents the length of the longest substring starting from s[i] that is also a prefix of the string s. s = "aaabaab":
Z[0] is undefined (commonly set to 0).Z[1] = 2 because the longest substring starting at s[1] is "aa" that also matches the prefix of s."aaabaab" will be: Z = [0, 2, 1, 0, 2, 1, 0]
S = P + '$' + T
Z[i] = m, then the substring starting at position i - (m + 1) in T matches P.
The Z-algorithm uses the Z-array which contains for every index, the length of the longest substring starting from that particular index which is also a prefix of the string. Thus, the pattern P that needs to be matched is kept as prefix in the string S and then the Z-array can be used to find all the indices where the pattern P is found in the text T string.
i, compare S[i] (substring starting at i) with the prefix S[0]. Calculate the number of matching characters for each i.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Compute the Z array for the combined string
vector<int> computeZarray(string s) {
int n = s.size(); // size of string
vector<int> Z(n, 0); // Z-array
// For every character
for(int i=1; i < n; i++) {
// Increment Z[i] till the characters matches with the prefix
while(i + Z[i] < n && s[i + Z[i]] == s[Z[i]]) Z[i]++;
}
return Z; // Return the computed Z-array
}
public:
// Function to find all indices of pattern in text
vector<int> search(string text, string pattern) {
string s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
vector<int> Z = computeZarray(s);
// Length of pattern and text
int n = text.size(), m = pattern.size();
// To store the result
vector<int> ans;
// Iterate on the combined string after the delimiter
for(int i = m+1; i < s.size(); i++) {
if(Z[i] == m) ans.push_back(i - (m + 1));
}
return ans;
}
};
int main() {
string text = "xyzabxyzabxyz";
string pattern = "xyz";
// Creating an instance of the solution class
Solution sol;
// Function call to find all indices of pattern in text
vector<int> ans = sol.search(text, pattern);
for(auto ind : ans) cout << ind << " ";
return 0;
}import java.util.*;
class Solution {
// Compute the Z array for the combined string
private int[] computeZarray(String s) {
int n = s.length(); // size of string
int[] Z = new int[n]; // Z-array
// For every character
for(int i = 1; i < n; i++) {
// Increment Z[i] till the characters matches with the prefix
while(i + Z[i] < n && s.charAt(i + Z[i]) == s.charAt(Z[i])) {
Z[i]++;
}
}
return Z; // Return the computed Z-array
}
// Function to find all indices of pattern in text
public List<Integer> search(String text, String pattern) {
String s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
int[] Z = computeZarray(s);
// Length of pattern and text
int n = text.length(), m = pattern.length();
// To store the result
List<Integer> ans = new ArrayList<>();
// Iterate on the combined string after the delimiter
for(int i = m+1; i < s.length(); i++) {
if(Z[i] == m) ans.add(i - (m + 1));
}
return ans;
}
}
class Main {
public static void main(String[] args) {
String text = "xyzabxyzabxyz";
String pattern = "xyz";
// Creating an instance of the solution class
Solution sol = new Solution();
// Function call to find all indices of pattern in text
List<Integer> ans = sol.search(text, pattern);
for(int ind : ans) {
System.out.print(ind + " ");
}
}
}
class Solution:
# Compute the Z array for the combined string
def computeZarray(self, s):
n = len(s) # size of string
Z = [0] * n # Z-array
# For every character
for i in range(1, n):
# Increment Z[i] till the characters matches with the prefix
while i + Z[i] < n and s[i + Z[i]] == s[Z[i]]:
Z[i] += 1
return Z # Return the computed Z-array
# Function to find all indices of pattern in text
def search(self, text, pattern):
s = pattern + '$' + text # Combined string
# Function call to find the Z array for the combined string
Z = self.computeZarray(s)
# Length of pattern and text
n = len(text)
m = len(pattern)
# To store the result
ans = []
# Iterate on the combined string after the delimiter
for i in range(m+1, len(s)):
if Z[i] == m:
ans.append(i - (m + 1))
return ans
if __name__ == "__main__":
text = "xyzabxyzabxyz"
pattern = "xyz"
# Creating an instance of the solution class
sol = Solution()
# Function call to find all indices of pattern in text
ans = sol.search(text, pattern)
for ind in ans:
print(ind, end=" ")
class Solution {
// Compute the Z array for the combined string
computeZarray(s) {
let n = s.length; // size of string
let Z = new Array(n).fill(0); // Z-array
// For every character
for(let i = 1; i < n; i++) {
// Increment Z[i] till the characters matches with the prefix
while(i + Z[i] < n && s[i + Z[i]] === s[Z[i]]) {
Z[i]++;
}
}
return Z; // Return the computed Z-array
}
// Function to find all indices of pattern in text
search(text, pattern) {
let s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
let Z = this.computeZarray(s);
// Length of pattern and text
let n = text.length, m = pattern.length;
// To store the result
let ans = [];
// Iterate on the combined string after the delimiter
for(let i = m + 1; i < s.length; i++) {
if(Z[i] === m) ans.push(i - (m + 1));
}
return ans;
}
}
// Example usage:
let text = "xyzabxyzabxyz";
let pattern = "xyz";
// Creating an instance of the solution class
let sol = new Solution();
// Function call to find all indices of pattern in text
let ans = sol.search(text, pattern);
for(let ind of ans) {
process.stdout.write(ind + " ");
}
Time Complexity: O(N2), where N is the length of the combined string S
Computing the Z-array using brute force takes O(N2) time and finding the matches requires iterating on the Z-array taking O(N) time.
Space Complexity: O(N), to store the Z-array.
The better approach includes computing the Z-array using a modified approach.
while loop to match characters against the prefix, resulting in a worst-case time complexity of O(N²) when all characters are identical. i is inside the window and the mirrored index i - left has a Z-value within bounds, reuse it (Z[i] = Z[i - left]).
Let's take an example: text = "abacaba", pattern = "aba"
We construct s = "aba$abacaba and compute Z function for it.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Compute the Z array for the combined string
vector<int> computeZarray(string s) {
int n = s.size(); // size of string
vector<int> Z(n, 0); // Z-array
// Pointers to mark the window
int left = 0, right = 0;
// For every character
for(int i=1; i < n; i++) {
// Out of window
if(i > right) {
while(i + Z[i] < n && s[i+Z[i]] == s[Z[i]])
Z[i]++;
}
// Else (Inside the window)
else {
// Check for inside
if(i + Z[i - left] <= right) Z[i] = Z[i - left];
// Else compute again using brute force method
else {
Z[i] = right - i + 1; // Take the answer till boundary
// Start matching beyond boundary using brute force
while(i + Z[i] < n && s[i + Z[i]] == s[Z[i]]) Z[i]++;
}
}
left = i, right = i + Z[i] - 1; // Update the window
}
return Z; // Return the computed Z-array
}
public:
// Function to find all indices of pattern in text
vector<int> search(string text, string pattern) {
string s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
vector<int> Z = computeZarray(s);
// Length of pattern and text
int n = text.size(), m = pattern.size();
// To store the result
vector<int> ans;
// Iterate on the combined string after the delimiter
for(int i = m+1; i < s.size(); i++) {
if(Z[i] == m) ans.push_back(i - (m + 1));
}
return ans;
}
};
int main() {
string text = "xyzabxyzabxyz";
string pattern = "xyz";
// Creating an instance of the solution class
Solution sol;
// Function call to find all indices of pattern in text
vector<int> ans = sol.search(text, pattern);
for(auto ind : ans) cout << ind << " ";
return 0;
}import java.util.*;
class Solution {
// Compute the Z array for the combined string
private int[] computeZarray(String s) {
int n = s.length(); // size of string
int[] Z = new int[n]; // Z-array
// Pointers to mark the window
int left = 0, right = 0;
// For every character
for(int i = 1; i < n; i++) {
// Out of window
if(i > right) {
while(i + Z[i] < n && s.charAt(i + Z[i]) == s.charAt(Z[i])) {
Z[i]++;
}
}
// Else (Inside the window)
else {
// Check for inside
if(i + Z[i - left] <= right) {
Z[i] = Z[i - left];
}
// Else compute again using brute force method
else {
Z[i] = right - i + 1; // Take the answer till boundary
// Start matching beyond boundary using brute force
while(i + Z[i] < n && s.charAt(i + Z[i]) == s.charAt(Z[i])) {
Z[i]++;
}
}
}
left = i;
right = i + Z[i] - 1; // Update the window
}
return Z; // Return the computed Z-array
}
// Function to find all indices of pattern in text
public List<Integer> search(String text, String pattern) {
String s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
int[] Z = computeZarray(s);
// Length of pattern and text
int n = text.length(), m = pattern.length();
// To store the result
List<Integer> ans = new ArrayList<>();
// Iterate on the combined string after the delimiter
for(int i = m+1; i < s.length(); i++) {
if(Z[i] == m) {
ans.add(i - (m + 1));
}
}
return ans;
}
}
class Main {
public static void main(String[] args) {
String text = "xyzabxyzabxyz";
String pattern = "xyz";
// Creating an instance of the solution class
Solution sol = new Solution();
// Function call to find all indices of pattern in text
List<Integer> ans = sol.search(text, pattern);
for(int ind : ans) {
System.out.print(ind + " ");
}
}
}
class Solution:
# Compute the Z array for the combined string
def computeZarray(self, s):
n = len(s) # size of string
Z = [0] * n # Z-array
# Pointers to mark the window
left, right = 0, 0
# For every character
for i in range(1, n):
# Out of window
if i > right:
while i + Z[i] < n and s[i + Z[i]] == s[Z[i]]:
Z[i] += 1
# Else (Inside the window)
else:
# Check for inside
if i + Z[i - left] <= right:
Z[i] = Z[i - left]
# Else compute again using brute force method
else:
Z[i] = right - i + 1 # Take the answer till boundary
# Start matching beyond boundary using brute force
while i + Z[i] < n and s[i + Z[i]] == s[Z[i]]:
Z[i] += 1
left, right = i, i + Z[i] - 1 # Update the window
return Z # Return the computed Z-array
# Function to find all indices of pattern in text
def search(self, text, pattern):
s = pattern + '$' + text # Combined string
# Function call to find the Z array for the combined string
Z = self.computeZarray(s)
# Length of pattern and text
n, m = len(text), len(pattern)
# To store the result
ans = []
# Iterate on the combined string after the delimiter
for i in range(m+1, len(s)):
if Z[i] == m:
ans.append(i - (m + 1))
return ans
if __name__ == "__main__":
text = "xyzabxyzabxyz"
pattern = "xyz"
# Creating an instance of the solution class
sol = Solution()
# Function call to find all indices of pattern in text
ans = sol.search(text, pattern)
for ind in ans:
print(ind, end=" ")
class Solution {
// Compute the Z array for the combined string
computeZarray(s) {
let n = s.length; // size of string
let Z = new Array(n).fill(0); // Z-array
// Pointers to mark the window
let left = 0, right = 0;
// For every character
for(let i = 1; i < n; i++) {
// Out of window
if(i > right) {
while(i + Z[i] < n && s[i + Z[i]] === s[Z[i]]) {
Z[i]++;
}
}
// Else (Inside the window)
else {
// Check for inside
if(i + Z[i - left] <= right) {
Z[i] = Z[i - left];
}
// Else compute again using brute force method
else {
Z[i] = right - i + 1; // Take the answer till boundary
// Start matching beyond boundary using brute force
while(i + Z[i] < n && s[i + Z[i]] === s[Z[i]]) {
Z[i]++;
}
}
}
left = i;
right = i + Z[i] - 1; // Update the window
}
return Z; // Return the computed Z-array
}
// Function to find all indices of pattern in text
search(text, pattern) {
let s = pattern + '$' + text; // Combined string
// Function call to find the Z array for the combined string
let Z = this.computeZarray(s);
// Length of pattern and text
let n = text.length, m = pattern.length;
// To store the result
let ans = [];
// Iterate on the combined string after the delimiter
for(let i = m + 1; i < s.length; i++) {
if(Z[i] === m) {
ans.push(i - (m + 1));
}
}
return ans;
}
}
// Example usage:
let text = "xyzabxyzabxyz";
let pattern = "xyz";
// Creating an instance of the solution class
let sol = new Solution();
// Function call to find all indices of pattern in text
let ans = sol.search(text, pattern);
for(let ind of ans) {
process.stdout.write(ind + " ");
}
Time Complexity: O(N), where N is the length of the combined string S
Computing the Z-array using modified approach takes O(N) time as each character of the string is processed at most once. And finding the matches requires iterating on the Z-array taking O(N) time.
Space Complexity: O(N), to store the Z-array.
Q: Why use the Z-function instead of other algorithms like KMP?
A: The Z-function preprocesses the entire string in O(n) and does not require a separate prefix function computation like KMP. It is easier to implement and works well for single pattern searching.
Q: How does the Z-function ensure pattern matching?
A: The Z-array computes the longest matching prefix starting at each position. If Z[i] == len(pattern), the pattern occurs at i - (len(pattern) + 1) in text.
Q: How does the Z-function compare to Rabin-Karp for multiple pattern searches?
A: Z-function is deterministic (O(n)), while Rabin-Karp relies on hashing and can degrade to O(nm) in worst cases.
Q: Can we modify the Z-function for approximate string matching?
A: Yes, instead of exact matches, allow a threshold edit distance using dynamic programming techniques.