Failure Function

vector<int> failure_function(const string& s) {
    vector<int> failure(s.length(), -1);
    
    int p = -1;
    for (int i = 1; s[i]; ++i) {
        while (p != -1 && s[p + 1] != s[i]) 
            p = failure[p];
        
        if (s[p + 1] == s[i]) ++p;
        failure[i] = p;
    }
    
    return failure;
}

KMP

vector<int> kmp(const string& s, const vector<int>& failure, const string& target) {
    vector<int> position;
    
    int p = -1;
    for (int i = 0; target[i]; ++i) {
        while (p != -1 && s[p + 1] != target[i])
            p = failure[p];
            
        if (s[p + 1] == target[i]) ++p;
        
        if (!s[p + 1]) {
            position.push_back(i - p);
            p = failure[p];
        }
    }
    
    return position;
}