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

vector<int> array_temporario(string & padrao){
    vector<int> index; int j, i;
    for(i = 0; i < padrao.length();)
        if(padrao[i] == padrao[j]){
            index[i] = j + 1; j++; i++;
        } else {
            index[i] = 0; i++;
        }
    return index;
}

bool KMP(string & texto, string & padrao){
    vector<int> index = array_temporario(padrao);
    int i = 0, j = 0;
    while(i < texto.length() && j < padrao.length()){
        if(texto[i] == padrao[j]){
            i++; j++;
        } else {
            if(j != 0) j = index[j-1];
            else i++;
        }
    }
    if(j == padrao.length()) return true;
    return false;
}

int main(){
    string texto = "abcxabcdabcdabcy", padrao = "abcdabcy";
    cout << KMP(texto, padrao) << endl;
}