Z-algorithm

#include<bits/stdc++.h>
#define ll long long

// Return an array result 
// result[i] is the maximum number x that base[i:i+x] equals to pattern[:x]
int* Zalgo(string base, int base_size, string pattern, int pattern_size) {
    
    string s = pattern + base;
    
    int n = pattern_size + base_size;
    int z[n];
    
    int L = 0, R = 0;
    for (int i = 1; i < n; i++) {
        if (i > R) {
            L = R = i;
            while (R < n && s[R - L] == s[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 && s[R - L] == s[R]) R++;
                z[i] = R - L; R--;
            }
        }
    }
    
    int *result = new int[base_size];
    for (int i = pattern_size; i < n; ++i) {
        result[i - pattern_size] = min(z[i], pattern_size);
    }
    
    return result;
}