Learnings Z-Function, Golang

TLDR - Got my hands dirty on golang, and learned a algorithm while doing a LC problem z_function.

About Z-Function

Z-Function is an really important and fundamental algorithm for strings. Z-Function of a string s of length N is an array z of same length where z[i] is the length of string starting at index i of s which is also prefix of s.

z[0] is not defined. It can be 0 or len(s) depending on usecase.

Java Implementation

Naive

public int[] z_function_naive(String s){
    int n = s.length();
    int[] z = new int[n];
    for(int i=1; i<n; i++){
        while(i+z[i] < n && s.charAt(z[i])==s.charAt(i+z[i])){
             z[i]++;
        }
    }
    return z;
}

Optimized

public int[] z_function(String s){
    int n = s.length();
    int l = 0, r = 0;
    int[] z = new int[n];
    for(int i=1; i<n ;i++){
        if(i<r){
            z[i] = Math.min(r-i, z[i-l]);
        }

        while(i+z[i] < n && s.charAt(z[i])==s.charAt(i+z[i])){
            z[i]++;
        }
        if(i+z[i] > r){
            l = i; r = i+z[i];
        }
    }
    return z;
}

I have yet to understand the complete reasoning behind the algorithm.

This is it for the week.