KMP_next_array.cpp

vector<int> getNext(const string& s) {
    vector<int> res(s.length());
    res[0] = -1;
    const char* start = s.c_str();
    int j = -1;
    for(int i = 0; i < s.length() - 1; ) {
        if(j == -1) {
            res[i + 1] = 0;
            i++;
            j = 0;
            continue;
        }
        if(start[i] == start[j]) {
            res[i + 1] = j + 1;
            j++;
            i++;
        } else {
            j = res[j];
        }
    }
    return res;
}