Z-Algorithm — Linear Prefix Matching for All Positions

s = "aabcaab"
z = [-, 1, 0, 0, 3, 1, 0]
        ^ ^ ^ ^ ^
        z[4]=3: s[4..6]="aab" matches s[0..2]="aab"

Maintain [l, r]: rightmost Z-box s[l..r]
For each i:
  If i < r: z[i] = min(r-i+1, z[i-l])  (use previous result)
  Extend z[i] naively
  Update [l, r] if extended past r

def z_function(s):
    n = len(s)
    z = [0]*n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r-i+1, z[i-l])
        while i+z[i] < n and s[z[i]] == s[i+z[i]]:
            z[i] += 1
        if i+z[i]-1 > r:
            l, r = i, i+z[i]-1
    return z

def z_search(text, pattern):
    combined = pattern + '$' + text
    z = z_function(combined)
    m = len(pattern)
    return [i-m-1 for i in range(m+1, len(combined)) if z[i] == m]

function zFunction(s) {
    const n=s.length, z=new Array(n).fill(0); z[0]=n;
    let l=0,r=0;
    for(let i=1;i<n;i++){
        if(i<r)z[i]=Math.min(r-i+1,z[i-l]);
        while(i+z[i]<n&&s[z[i]]===s[i+z[i]])z[i]++;
        if(i+z[i]-1>r){l=i;r=i+z[i]-1;}
    }
    return z;
}
function zSearch(text,pat){
    const s=pat+'$'+text,z=zFunction(s),m=pat.length;
    return z.slice(m+1).map((v,i)=>v===m?i:-1).filter(i=>i>=0);
}

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

#include <vector>
#include <string>
using namespace std;
vector<int> zFunction(string s){
    int n=s.size(); vector<int>z(n,0); z[0]=n; int l=0,r=0;
    for(int i=1;i<n;i++){
        if(i<r)z[i]=min(r-i+1,z[i-l]);
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>r){l=i;r=i+z[i]-1;}
    }
    return z;
}

void zFunction(char*s,int*z,int n){
    z[0]=n; int l=0,r=0;
    for(int i=1;i<n;i++){
        if(i<r)z[i]=(r-i+1)<z[i-l]?(r-i+1):z[i-l];
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>r){l=i;r=i+z[i]-1;}
    }
}