#include <iostream>
#include <bits/stdc++.h>
using namespace std;

vector<int> sufix_and_prefix(string pattern) {
    vector<int> aux;
    aux.resize(pattern.size(), 0);

    int i = 0;
    int j = 1;

    while(j < pattern.size()){
        if(pattern[i] == pattern[j]) {
            aux[j] = i + 1;
            i++;
            j++;
        } else if(i != 0){
            i = aux[i - 1];
        } else {
            aux[j] = 0;
            j++;
        }
    }

    return aux;
}

bool KMP(string s, string pattern){
    vector<int> aux = sufix_and_prefix(pattern);
    int i = 0;
    int j = 0;
    while(i < s.size() && j < pattern.size()) {
        if(s[i] == pattern[j]) {
            i++;
            j++;
        } else {
            if(j != 0) {
                j = aux [j - 1];
            } else {
                i++;
            }
        }
    }
    if(j == pattern.size())
            return true;


    return false;
}
int main()
{
    string str = "abcxabcdabcdabcy";
    string subString = "abcdabcy";
    cout<< KMP(str, subString);
    return 0;
}