Z Algorithm

Definition

Definition

The Z Algorithm is a linear time pattern matching algorithm used to find all occurrences of a pattern in a given text. It preprocesses the pattern to create a Z-array, which stores the longest common prefix between the pattern and every suffix of the pattern. This array is then utilized to efficiently find matches in the text

Explanation

Preprocesses the pattern and text to construct a Z-array, where each element Z[i] represents the length of the longest substring starting from index i that matches the prefix of the pattern. By comparing the Z-array values with the length of the pattern, we can identify positions in the text where the pattern occurs

Guidance

• Preprocess the pattern and text to construct the Z-array
• Initialize two pointers, L and R, where L left boundary and R right boundary of the current match
• Iterate through the text
  • update R to the maximum index where Z[R-L] equals the length of the pattern or until the end of the text
  • if R exceeds the current right boundary, update L and R accordingly
  • if R reaches the end of the pattern, record the starting index of the match

Tips

• utilize the Z-array efficiently to avoid unnecessary comparisons
• consider edge cases such as empty pattern or text

Practice

Practice

ZAlgorithm(text, pattern):
  concat = pattern + "$" + text
  Z = [0] * length(concat)
  L = 0
  R = 0

  for i from 1 to length(concat) - 1:
    if i > R:
      L = R = i
      while R < length(concat) and concat[R - L] == concat[R]:
        R += 1
      Z[i] = R - L
      R -= 1
    else:
      k = i - L
      if R - i + 1 > Z[k]:
        Z[i] = Z[k]
      else:
        L = i
        while R < length(concat) and concat[R - L] == concat[R]:
          R += 1
        Z[i] = R - L
        R -= 1

  matches = []
  for i from length(pattern) + 1 to length(concat) - 1:
    if Z[i] == length(pattern):
      matches.append(i - length(pattern) - 1)

  return matches

Solution

package main

func zAlgorithm(text string) []int {
	n := len(text)
	z := make([]int, n)
	var l, r int
	for i := 1; i < n; i++ {
		if i <= r {
			z[i] = min(r-i+1, z[i-l])
		}
		for i+z[i] < n && text[z[i]] == text[i+z[i]] {
			z[i]++
		}
		if i+z[i]-1 > r {
			l = i
			r = i + z[i] - 1
		}
	}
	return z
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

import java.util.Arrays;

public class ZAlgorithm {

  public static int[] zAlgorithm(String text) {
    int n = text.length();
    int[] z = new int[n];
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
      if (i <= r) {
        z[i] = Math.min(r - i + 1, z[i - l]);
      }
      while (i + z[i] < n && text.charAt(z[i]) == text.charAt(i + z[i])) {
        z[i]++;
      }
      if (i + z[i] - 1 > r) {
        l = i;
        r = i + z[i] - 1;
      }
    }
    return z;
  }
}

function zAlgorithm(text) {
  const n = text.length;
  const z = new Array(n).fill(0);
  let l = 0,
    r = 0;
  for (let i = 1; i < n; i++) {
    if (i <= r) {
      z[i] = Math.min(r - i + 1, z[i - l]);
    }
    while (i + z[i] < n && text.charAt(z[i]) === text.charAt(i + z[i])) {
      z[i]++;
    }
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

fun zAlgorithm(text: String): IntArray {
    val n = text.length
    val z = IntArray(n)
    var l = 0
    var r = 0
    for (i in 1 until n) {
        if (i <= r) {
            z[i] = minOf(r - i + 1, z[i - l])
        }
        while (i + z[i] < n && text[z[i]] == text[i + z[i]]) {
            z[i]++
        }
        if (i + z[i] - 1 > r) {
            l = i
            r = i + z[i] - 1
        }
    }
    return z
}

def z_algorithm(text):
    n = len(text)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and text[z[i]] == text[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z

fn z_algorithm(text: &str) -> Vec<usize> {
    let n = text.len();
    let mut z = vec![0; n];
    let (mut l, mut r) = (0, 0);
    for i in 1..n {
        if i <= r {
            z[i] = (r - i + 1).min(z[i - l]);
        }
        while i + z[i] < n && text.as_bytes()[z[i]] == text.as_bytes()[i + z[i]] {
            z[i] += 1;
        }
        if i + z[i] - 1 > r {
            l = i;
            r = i + z[i] - 1;
        }
    }
    z
}

function zAlgorithm(text: string): number[] {
  const n = text.length;
  const z: number[] = new Array(n).fill(0);
  let l = 0,
    r = 0;
  for (let i = 1; i < n; i++) {
    if (i <= r) {
      z[i] = Math.min(r - i + 1, z[i - l]);
    }
    while (i + z[i] < n && text[z[i]] === text[i + z[i]]) {
      z[i]++;
    }
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}