int back[MAXN];
string S, P;

void kmpPreprocess() {
    int j = -1;
    back[0] = -1;
    for (int i = 0; i < P.size(); i++) {
        while (j >= 0 && P[i] != P[j])
            j = back[j];
        j++;
        back[i + 1] = j;
    }
}

vector<int> kmpSearch(string S) {
    vector<int> res;
    int j = 0;
    for (int i = 0; i < S.size(); i++) {
        while (j >= 0 && S[i] != P[j])
            j = back[j];
        j++;
        if (j == P.size()) {
            res.push_back(i - P.size() + 1);
            j = back[j];
        }
    }
    return res;
}