kmp

//kmp

vector<ll> calcu(string &s) {
    vector<ll> pi(s.size());
    for(int i = 1; i < s.size(); i++) {
        int j = pi[i-1];
        while(j > 0 && s[j] != s[i]) j = pi[j-1];
        if(s[j] == s[i]) ++j;
        pi[i] = j;
    }
    return pi;
}