Z-function

// Naive realization

std::vector<int> zFunction(std::string s) {
    int n = (int)(s.length());
    std::vector<int> zf(n);
    zf[0] = 0;
    for (int i = 0; i < n; ++i) {
        while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]]) zf[i]++;
    }

    return zf;
}

// Effective realization

std::vector<int> effectiveZFunction(std::string s) {
    int n = (int)(s.length());
    int left = 0, right = 0;
    std::vector<int> zf(n);
    for (int i = 0; i < n; ++i) {
        zf[i] = max(0, min(right - i, zf[i - left]));
        while (zf[i] < n && s[zf[i]] == s[i + zf[i]]) zf[i]++;
        if (i + zf[i] > right) {
            left = i;
            right = i + zf[i];
        }
    }

    return zf;
}