Z Algorithm

Explanation

- The **Z Algorithm** is a string matching algorithm that provides efficient matching of **prefixes** within a string. It represents the string as an array where each index in the array holds a **Z-value**. The Z-value at each index represents the length of the longest substring starting from that index which is also a prefix of the string.

-

• Steps:

  • Compute the Z-array for the given string.
  • The Z-value at each index tells the length of the matching prefix starting from that index.
  • If a Z-value matches the length of the pattern, it indicates a match at that position.

• Time Complexity:

  • The time complexity of the Z Algorithm is O(n), where n is the size of the string.