KMP

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