z-function

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] = std::max(0, std::min(right - i, zf[i - left]));
        while (i + 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;
}