Understanding KMP

Useful links for understanding.

• Understand how kmp works, Post by Ruanyi Feng

• Understand how to calculate the next table, post from Zhihu

My implementation of calculate next table.

vector<int> cal_next(string s) {
    vector<int> next(s.size(), 0);
    
    int j = 0; // keep track of the pointer it should match
    for (int i = 1; i < s.size(); ++i) {
        while (j > 0 && s[i] != s[j]) j = next[j-1];
        if (s[i] == s[j]) { j++; } 
        next[i] = j;
    }
    return next;
}