Z algorithm (Linear time pattern searching Algorithm)

This is a linear time pattern searching algorithm used to find all occurrences of a pattern within a text. It preprocesses the pattern to construct a Z-array, which contains information about the longest substring starting from each position that matches the prefix of the pattern.

Algorithm:

1. Construct the Z-array:

- Concatenate a special character (typically '$') and the text.

- Initialize two pointers, "left" and "right," at the start of the concatenated string.

- Iterate from position 1 to the end of the concatenated string:

- If current position > right pointer, find length of the longest prefix starting from this position that matches the prefix of the pattern.

- Update the left and right pointers.

- Store the length of the matching substring in the Z-array.

2. Find pattern matches:

- Iterate through the Z-array starting from the position equal to the pattern length.

- If the value in the Z-array is equal to the pattern length, a match is found at the corresponding position in the text.

However, it is important to note that the Z algorithm may require additional space for the Z-array, which can be of the same length as the concatenated string.

This process has a time complexity of O(n + m) due to the linear scan of the concatenated string.