#include <iostream>
#include <vector>

using namespace std;

vector<int> KMP_generate(string P, int m) {
    vector<int> S(m);
    S[0] = -1;
// P[k+1] to potencjalny kandydat podciagu
    for(int i = 1, k = -1; i < m; ++i) {
        while(k > -1 && P[k + 1] != P[i])
            k = S[k];
        if(P[k + 1] == P[i]) // jeszcze nie koniec
            ++k;
        S[i] = k;
    }
    return S;
}


int main() {
    string znaki="aaabaccaaabaaababcaa";
    vector<int> wygenerowany= KMP_generate(znaki,znaki.size());
    for (const auto &item : wygenerowany)
        cout<<item+1<<" ";

    return 0;
}