#include <iostream>
using namespace std;
const int maxn = 1e5 + 10;
int lps[maxn];
void preprocess_lps(string pattern) {
    int j = 0, i = 1;
    lps[0] = 0;

    while(i < (int) pattern.size()) {
        if(pattern[i] == pattern[j]) {
            lps[i] = j + 1;
            j++;
            i++;
        }
        else {
            if(j != 0) {
                j = lps[j - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}
void kmp(string text, string pattern) {
    int n = (int) text.size();
    int m = (int) pattern.size();
    preprocess_lps(pattern);
    int i = 0, j = 0;
    while(n - i >= m - j) {
        if(text[i] == pattern[j]) {
            i++;
            j++;
        }
        if(j == m) {
            cout << "found at index: " << i - j << endl;
            j = lps[j - 1];
        }
        else if(i < n and text[i] != pattern[j]) {
            if(j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
    }
}

int main() {

    kmp("abxabcabcaby", "abcaby");
   return 0;
}