**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.