# z-algorithm

void match(vector<int> &z, string s){
    int len=s.size();
    z[0]=0;
    int l=0, r=0;
    rep(i,1,len){
        if(i<=r) z[i]=min(z[i-l], r-i+1);
        while(i+z[i]<len && s[z[i]] == s[i+z[i]]) z[i]++;
        if(i+z[i]-1>r) l=i, r=i+z[i]-1;
    }
}