#include<vector>
#include<string>
 
int knuth_morris_pratt_count(std::string s, std::string t) {  // Counts all occurrences of string t in string s
    std::vector<int> kmp(t.size()+1, 0);  // In `t`, maximum prefix [0, kmp[pos]) that corresponds to suffix of [0, pos)
    for(int i=1; i<(int)t.size(); i++) {
        kmp[i+1] = kmp[i];
        while(kmp[i+1] > 0 && t[i] != t[kmp[i+1]]) {  // While end doesn't match t[i]
            kmp[i+1] = kmp[kmp[i+1]];  // Go back along prefixes
        }
        if(t[i] == t[kmp[i+1]]) kmp[i+1]++;  // If match, then extend prefix
    }
    
    int match_len = 0;  // Maximum prefix of `t` we have matched in current position of `s`
    int result = 0;  // Count of occurrences
    for(char c : s) {
        if(match_len == (int)t.size()) {
            match_len = kmp[match_len];  // If match, then go back a prefix
        }
        while(match_len > 0 && c != t[match_len]) {  // While prefix can't be extended
            match_len = kmp[match_len];  // Go back a prefix
        }
        if(c == t[match_len]) {  // Extend prefix length if we can
            match_len++;
        }
        if(match_len == (int)t.size()) result++;  // Match found
    }
    return result;
}

int main() {
    std::string s = "abacababa";
    std::string t = "aba";
    int result = knuth_morris_pratt_count(s, t);
    return 0;
}