1. Introduction

The Z-Algorithm is a linear time pattern searching algorithm that helps find all occurrences of a pattern in a text. It constructs a Z-array which can be used for pattern matching.

2. Program Steps

1. Construct a new string by concatenating the pattern, a special character (usually $), and the text.

2. Build the Z-array for this concatenated string.

3. The Z-values at any index i in this array represent the length of the substring which starts from i and is also a prefix of the concatenated string.

4. Wherever the Z-value equals the length of the pattern, we have a pattern match.

3. Code Program

public class ZAlgorithm {

    // Construct Z-array for given string
    private static int[] constructZArray(String str) {
        int n = str.length();
        int[] Z = new int[n];

        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i > r) {
                l = r = i;
                while (r < n && str.charAt(r - l) == str.charAt(r))
                    r++;
                Z[i] = r - l;
                r--;
            } else {
                int k = i - l;
                if (Z[k] < r - i + 1)
                    Z[i] = Z[k];
                else {
                    l = i;
                    while (r < n && str.charAt(r - l) == str.charAt(r))
                        r++;
                    Z[i] = r - l;
                    r--;
                }
            }
        }
        return Z;
    }

    public static void searchPattern(String text, String pattern) {
        String concat = pattern + "$" + text;
        int[] Z = constructZArray(concat);

        for (int i = 0; i < Z.length; i++) {
            if (Z[i] == pattern.length()) {
                System.out.println("Pattern found at index: " + (i - pattern.length() - 1));
            }
        }
    }

    public static void main(String[] args) {
        String text = "GEEKS FOR GEEKS";
        String pattern = "GEEK";
        searchPattern(text, pattern);
    }
}

Output:

Pattern found at index: 0
Pattern found at index: 10

4. Step By Step Explanation

1. The constructZArray function builds the Z-array for the given string. This array will contain for each index i the length of the substring starting from i which is also a prefix of the input string.

2. The searchPattern function creates the concatenated string by adding the pattern, a special character ($), and then the text. This concatenated string is then used to construct the Z-array.

3. We then traverse the Z-array. For each index i, if the value at Z[i] is equal to the length of the pattern, it indicates that the pattern has been found in the text at index i – pattern.length() – 1.

4. The provided main method searches for the pattern "GEEK" in the text "GEEKS FOR GEEKS". The pattern is found at indices 0 and 10 in the text.