#include <iostream>
#include <string>
#include <vector>

void PrefixFunction(const std::string& str, std::vector<int>& prefix){
    int i, j;
    j = 0;
    prefix[0] = 0;
    for (i = 1; i < prefix.size(); i++) {
        while (j > 0 && str[j] != str[i]) {
            j = prefix[j - 1];
        }

        if (str[i] == str[j]) {
            j++;
        }
        prefix[i] = j;
    }
}

void KMP(const std::string& str, const std::string& word){
    int i, j;

    i = 0;
    j = 0;

    std::vector<int> prefix(str.size());
    PrefixFunction(word, prefix);


    while (i < str.size()) {
        while(str[i] == word[j] && j < word.size() && i < str.size()){
            i++;
            j++;
        }
        if(j == word.size()){
            std::cout << "match at: " << i - word.size() << std::endl;
            j = 0;
        } else {
            if (j > 0){
                j = prefix[j - 1];
            } else {
                std::cout << i<< ", " << j  << " inc" << std::endl;
                i++;
            }
        }
    }
}


int main(){
    KMP("abxabcabcaby", "abcaby");
    return 0;
}