CSES Solutions - String Functions

We consider a string of n characters, indexed 1,2,...,n . Your task is to calculate all values of the following functions:

• z(i) denotes the maximum length of a substring that begins at position i and is a prefix of the string. In addition, z(1)=0.
• π(i) denotes the maximum length of a substring that ends at position i, is a prefix of the string, and whose length is at most i-1.

Note that the function z is used in the Z-algorithm, and the function π(i) is used in the KMP algorithm

Example:

Input: s = "abaabca"
Output:
0 0 1 2 0 0 1
0 0 1 1 2 0 1

Input: s = "bbaabcb"
Output:
0 1 0 0 1 0 1
0 1 0 0 1 0 1

Approach: To solve the problem, follow the below idea:

First calculates the z(i) or Z-function using a two-pointer approach, which keeps track of the segment within which we are currently working. After calculating the z(i) function, prints the values.

Next, calculates the pi(i) function by iterating over the string and checking if the current character matches the character at the index equal to the pi(i) function of the previous position. If it does, it increments the pi(i) function for the current position. If it doesn’t, it finds the next smaller possible matching prefix and suffix by using the pi(i) function of the previous index until it finds a match or no more prefixes are left. After calculating the pi(i) function, it prints the values.

Step-by-step algorithm:

• Z-Function Calculation:
  • Initialize the Z-function array zFun to store the length of the longest common prefix between s and its suffix starting from each position.
  • Iterate through each position in the string starting from the second position.
  • If the current position is within the rightmost boundary (right), use precomputed values to initialize zFun[position].
  • Extend the Z-function by comparing characters while the characters match, updating zFun[position].
  • Update the boundaries (left and right) for the current palindrome.
  • Print the Z-function values.
• Prefix Function Calculation:
  • Initialize the prefix function array prefixFun to store the length of the longest proper prefix which is also a suffix for each position.
  • Iterate through each position in the string starting from the second position.
  • Use the previous value of the prefix function (prefixFun[position - 1]) to initialize j.
  • Update the prefix function using the previous values while characters don't match.
  • Increment the prefix function if characters match.
  • Update the prefix function for the current position.
  • Print the prefix function values.

Below is the implementation of above approach:

#include <cstring> #include <iostream> using namespace std; const int maxStringLength = 1e6 + 5; char s[maxStringLength]; int n, zFun[maxStringLength], prefixFun[maxStringLength]; int main() {  // Read the input string  string s = "bbaabcb";  int n = s.size();  // Calculate the Z-function for each position in the  // string  for (int position = 1, left = 0, right = 0;  position < n; position++) {  // If within the rightmost boundary, use precomputed  // values  if (position <= right)  zFun[position] = min(right - position + 1,  zFun[position - left]);  // Extend the Z-function by comparing characters  while (position + zFun[position] < n  && s[zFun[position]]  == s[position + zFun[position]])  zFun[position]++;  // Update the boundaries for the current palindrome  if (position + zFun[position] - 1 > right)  left = position,  right = position + zFun[position] - 1;  }  // Print the Z-function values  for (int i = 0; i < n; i++)  cout << zFun[i] << (" \n")[i == n - 1];  // Calculate the prefix function for each position in  // the string  for (int position = 1; position < n; position++) {  int j = prefixFun[position - 1];  // Update the prefix function using previous values  while (j > 0 && s[position] != s[j])  j = prefixFun[j - 1];  // Increment the prefix function if characters match  if (s[position] == s[j])  j++;  // Update the prefix function for the current  // position  prefixFun[position] = j;  }  // Print the prefix function values  for (int i = 0; i < n; i++)  cout << prefixFun[i] << (" \n")[i == n - 1];  return 0; } 

import java.util.*; public class Main {  // Define the maximum string length  static final int maxStringLength = (int) 1e6 + 5;  public static void main(String[] args) {  // Read the input string  String s = "bbaabcb";  int n = s.length();  // Initialize the Z-function and prefix function arrays  int[] zFun = new int[n];  int[] prefixFun = new int[n];  // Calculate the Z-function for each position in the string  for (int position = 1, left = 0, right = 0; position < n; position++) {  // If within the rightmost boundary, use precomputed values  if (position <= right) {  zFun[position] = Math.min(right - position + 1, zFun[position - left]);  }  // Extend the Z-function by comparing characters  while (position + zFun[position] < n && s.charAt(zFun[position]) == s.charAt(position + zFun[position])) {  zFun[position]++;  }  // Update the boundaries for the current palindrome  if (position + zFun[position] - 1 > right) {  left = position;  right = position + zFun[position] - 1;  }  }  // Print the Z-function values  System.out.print("Z-function values: ");  for (int value : zFun) {  System.out.print(value + " ");  }  System.out.println();  // Calculate the prefix function for each position in the string  for (int position = 1; position < n; position++) {  int j = prefixFun[position - 1];  // Update the prefix function using previous values  while (j > 0 && s.charAt(position) != s.charAt(j)) {  j = prefixFun[j - 1];  }  // Increment the prefix function if characters match  if (s.charAt(position) == s.charAt(j)) {  j++;  }  // Update the prefix function for the current position  prefixFun[position] = j;  }  // Print the prefix function values  System.out.print("Prefix function values: ");  for (int value : prefixFun) {  System.out.print(value + " ");  }  System.out.println();  } } 

# Define the maximum string length maxStringLength = int(1e6 + 5) def main(): # Read the input string s = "bbaabcb" n = len(s) # Initialize the Z-function and prefix function arrays zFun = [0]*n prefixFun = [0]*n # Calculate the Z-function for each position in the string for position in range(1, n): left = 0 right = 0 # If within the rightmost boundary, use precomputed values if position <= right: zFun[position] = min(right - position + 1, zFun[position - left]) # Extend the Z-function by comparing characters while position + zFun[position] < n and s[zFun[position]] == s[position + zFun[position]]: zFun[position] += 1 # Update the boundaries for the current palindrome if position + zFun[position] - 1 > right: left = position right = position + zFun[position] - 1 # Print the Z-function values print("Z-function values: ", zFun) # Calculate the prefix function for each position in the string for position in range(1, n): j = prefixFun[position - 1] # Update the prefix function using previous values while j > 0 and s[position] != s[j]: j = prefixFun[j - 1] # Increment the prefix function if characters match if s[position] == s[j]: j += 1 # Update the prefix function for the current position prefixFun[position] = j # Print the prefix function values print("Prefix function values: ", prefixFun) # Call the main function main() 

function GFG(s) {  let n = s.length;  let zFun = new Array(n).fill(0);  // Loop to calculate Z-function for the each position in the string  for (let position = 1, left = 0, right = 0; position < n; position++) {  if (position <= right) {  zFun[position] = Math.min(right - position + 1, zFun[position - left]);  }  // Extend the Z-function by the comparing characters  while (position + zFun[position] < n && s[zFun[position]] == s[position + zFun[position]]) {  zFun[position]++;  }  // Update the boundaries for the current palindrome  if (position + zFun[position] - 1 > right) {  left = position;  right = position + zFun[position] - 1;  }  }  return zFun; } // Function to calculate the prefix function for the given string function calculatePrefixFunction(s) {  let n = s.length;  let prefixFun = new Array(n).fill(0);  // Loop to calculate prefix function for each position in the string  for (let position = 1; position < n; position++) {  let j = prefixFun[position - 1];  // Update the prefix function using previous values  while (j > 0 && s[position] != s[j]) {  j = prefixFun[j - 1];  }  // Increment the prefix function if characters match  if (s[position] == s[j]) {  j++;  }  // Update the prefix function for current position  prefixFun[position] = j;  }  return prefixFun; } // Main function function main() {  let s = "bbaabcb";  // Calculate Z-function and prefix function  let zFun = GFG(s);  let prefixFun = calculatePrefixFunction(s);  console.log(zFun.join(" "));  console.log(prefixFun.join(" ")); } main(); 

0 1 0 0 1 0 1 0 1 0 0 1 0 1 

Time Complexity: O(n)
Auxiliary Space: O(n)