vector<int> zfunc(const string &w){
    vector<int> z(w.size());
    for(int l = 0, i = 1;i < w.size();++i){
        z[i] = max(0, min(l+z[l] - i, z[i-l]));
        while(i + z[i] < w.size() and w[i+z[i]] == w[z[i]])++z[i], l = i;
    }
    return z;
}